<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 2.2</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 2.2" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 2.2" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-2.xhtml#Chapter-2" rel="prev" title="Chapter 2" />
<link href="2_002e3.xhtml#g_t2_002e3" rel="next" title="2.3" />
<link href="2_002e1.xhtml#g_t2_002e1_002e4" rel="prev" title="2.1.4" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />

<script src="js/jquery.min.js" type="text/javascript"></script>
<script src="js/footnotes.js" type="text/javascript"></script>
<script src="js/browsertest.js" type="text/javascript"></script>
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t2_002e2"></a>
<nav class="header">
<p>
Next: <a href="2_002e3.xhtml#g_t2_002e3" accesskey="n" rel="next">2.3</a>, Prev: <a href="2_002e1.xhtml#g_t2_002e1" accesskey="p" rel="prev">2.1</a>, Up: <a href="Chapter-2.xhtml#Chapter-2" accesskey="u" rel="prev">Chapter 2</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Hierarchical-Data-and-the-Closure-Property"></a>
<h3 class="section"><span class="secnum">2.2</span><span class="sectitle">Hierarchical Data and the Closure Property</span></h3>

<p>As we have seen, pairs provide a primitive “glue” that we can use to
construct compound data objects.  <a href="#Figure-2_002e2">Figure 2.2</a> shows a standard way to
visualize a pair—in this case, the pair formed by <code>(cons 1 2)</code>.  In this
representation, which is called <a id="index-box_002dand_002dpointer-notation"></a>
<em>box-and-pointer notation</em>, each object
is shown as a <a id="index-pointer"></a>
<em>pointer</em> to a box.  The box for a primitive object
contains a representation of the object.  For example, the box for a number
contains a numeral.  The box for a pair is actually a double box, the left part
containing (a pointer to) the <code>car</code> of the pair and the right part
containing the <code>cdr</code>.
</p>
<figure class="float">
<a id="Figure-2_002e2"></a>
<object style="width: 21.76ex; height: 11.83ex;" data="fig/chap2/Fig2.2e.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.2:</strong> Box-and-pointer representation of <code>(cons 1 2)</code>.</p>
</figcaption>
</figure>

<p>We have already seen that <code>cons</code> can be used to combine not only numbers
but pairs as well.  (You made use of this fact, or should have, in doing
<a href="2_002e1.xhtml#Exercise-2_002e2">Exercise 2.2</a> and <a href="2_002e1.xhtml#Exercise-2_002e3">Exercise 2.3</a>.)  As a consequence, pairs provide a
universal building block from which we can construct all sorts of data
structures.  <a href="#Figure-2_002e3">Figure 2.3</a> shows two ways to use pairs to combine the
numbers 1, 2, 3, and 4.
</p>
<figure class="float">
<a id="Figure-2_002e3"></a>
<object style="width: 55.60ex; height: 28.41ex;" data="fig/chap2/Fig2.3e.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.3:</strong> Two ways to combine 1, 2, 3, and 4 using pairs.</p>
</figcaption>
</figure>

<p>The ability to create pairs whose elements are pairs is the essence of list
structure’s importance as a representational tool.  We refer to this ability as
the <a id="index-closure-property"></a>
<em>closure property</em> of <code>cons</code>.  In general, an operation for
combining data objects satisfies the closure property if the results of
combining things with that operation can themselves be combined using the same
operation.<a class="footnote_link" id="DOCF72" href="#FOOT72"><sup>72</sup></a> Closure
is the key to power in any means of combination because it permits us to create
<a id="index-hierarchical"></a>
<em>hierarchical</em> structures—structures made up of parts, which
themselves are made up of parts, and so on.
</p>
<p>From the outset of <a href="Chapter-1.xhtml#Chapter-1">Chapter 1</a>, we’ve made essential use of closure in
dealing with procedures, because all but the very simplest programs rely on the
fact that the elements of a combination can themselves be combinations.  In
this section, we take up the consequences of closure for compound data.  We
describe some conventional techniques for using pairs to represent sequences
and trees, and we exhibit a graphics language that illustrates closure in a
vivid way.<a class="footnote_link" id="DOCF73" href="#FOOT73"><sup>73</sup></a>
</p>

<a id="g_t2_002e2_002e1"></a>
<a id="Representing-Sequences"></a>
<h4 class="subsection"><span class="secnum">2.2.1</span><span class="sectitle">Representing Sequences</span></h4>

<p>One of the useful structures we can build with pairs is a
<a id="index-sequence"></a>
<em>sequence</em>—an ordered collection of data objects.  There are, of
course, many ways to represent sequences in terms of pairs.  One particularly
straightforward representation is illustrated in <a href="#Figure-2_002e4">Figure 2.4</a>, where the
sequence 1, 2, 3, 4 is represented as a chain of pairs.  The <code>car</code> of each
pair is the corresponding item in the chain, and the <code>cdr</code> of the pair is
the next pair in the chain.  The <code>cdr</code> of the final pair signals the end
of the sequence by pointing to a distinguished value that is not a pair,
represented in box-and-pointer diagrams as a diagonal line and in programs as
the value of the variable <code>nil</code>.  The entire sequence is constructed by
nested <code>cons</code> operations:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">1</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">2</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">3</span><span class="pln">
                  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> nil</span><span class="clo">))))</span></pre></div>

<figure class="float">
<a id="Figure-2_002e4"></a>
<object style="width: 48.95ex; height: 11.83ex;" data="fig/chap2/Fig2.4e.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.4:</strong> The sequence 1, 2, 3, 4 represented as a chain of pairs.</p>
</figcaption>
</figure>

<p>Such a sequence of pairs, formed by nested <code>cons</code>es, is called a
<a id="index-list"></a>
<em>list</em>, and Scheme provides a primitive called <code>list</code> to help in
constructing lists.<a class="footnote_link" id="DOCF74" href="#FOOT74"><sup>74</sup></a>  The above sequence could be produced by <code>(list 1 2 3 4)</code>.
In general,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">list ⟨</span><var><span class="pln">a</span><span class="pun">₁</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">a</span><span class="pun">₂</span></var><span class="pln">⟩ </span><span class="roman"><span class="pun">…</span></span><span class="pln"> ⟨</span><var><span class="pln">a</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>is equivalent to
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> ⟨</span><var><span class="pln">a</span><span class="pun">₁</span></var><span class="pln">⟩
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> ⟨</span><var><span class="pln">a</span><span class="pun">₂</span></var><span class="pln">⟩
            </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="roman"><span class="pun">…</span></span><span class="pln">
                  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> ⟨</span><var><span class="pln">a</span><span class="pun">ₙ</span></var><span class="pln">⟩
                        nil</span><span class="clo">)</span><span class="roman"><span class="pun">…</span></span><span class="clo">)))</span></pre></div>

<p>Lisp systems conventionally print lists by printing the sequence of elements,
enclosed in parentheses.  Thus, the data object in <a href="#Figure-2_002e4">Figure 2.4</a> is printed
as <code>(1 2 3 4)</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> one-through-four </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">))</span><span class="pln">

one-through-four
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span></i>
</pre></div>

<p>Be careful not to confuse the expression <code>(list 1 2 3 4)</code> with the list
<code>(1 2 3 4)</code>, which is the result obtained when the expression is
evaluated.  Attempting to evaluate the expression <code>(1 2 3 4)</code> will signal
an error when the interpreter tries to apply the procedure <code>1</code> to
arguments <code>2</code>, <code>3</code>, <code>4</code>.
</p>
<p>We can think of <code>car</code> as selecting the first item in the list, and of
<code>cdr</code> as selecting the sublist consisting of all but the first item.
Nested applications of <code>car</code> and <code>cdr</code> can be used to extract the
second, third, and subsequent items in the list.<a class="footnote_link" id="DOCF75" href="#FOOT75"><sup>75</sup></a> The constructor <code>cons</code>
makes a list like the original one, but with an additional item at the
beginning.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">car</span><span class="pln"> one-through-four</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">1</span></i><span class="pln">

</span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> one-through-four</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> one-through-four</span><span class="clo">))</span><span class="pln">
</span><i><span class="lit">2</span></i><span class="pln">

</span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">10</span><span class="pln"> one-through-four</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">10</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> one-through-four</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">5</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span></i>
</pre></div>

<p>The value of <code>nil</code>, used to terminate the chain of pairs, can be thought
of as a sequence of no elements, the <a id="index-empty-list"></a>
<em>empty list</em>.  The word
<a id="index-nil"></a>
<em>nil</em> is a contraction of the Latin word <em>nihil</em>, which means
“nothing.”<a class="footnote_link" id="DOCF76" href="#FOOT76"><sup>76</sup></a>
</p>
<a id="List-operations"></a>
<h5 class="subsubheading">List operations</h5>

<p>The use of pairs to represent sequences of elements as lists is accompanied by
conventional programming techniques for manipulating lists by successively
“<code>cdr</code>ing down” the lists.  For example, the procedure <code>list-ref</code>
takes as arguments a list and a number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> and returns the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> item of
the list.  It is customary to number the elements of the list beginning with 0.
The method for computing <code>list-ref</code> is the following:
</p>
<ul>
<li> For <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>=</mo>
    <mn>0</mn>
  </mrow>
</math>, <code>list-ref</code> should return the <code>car</code> of the list.

</li><li> Otherwise, <code>list-ref</code> should return  the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math>-st item of the
<code>cdr</code> of the list.

</li></ul>

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list-ref items n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> items</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">list-ref </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> items</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> squares 
  </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">9</span><span class="pln"> </span><span class="lit">16</span><span class="pln"> </span><span class="lit">25</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">list-ref squares </span><span class="lit">3</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">16</span></i>
</pre></div>

<p>Often we <code>cdr</code> down the whole list.  To aid in this, Scheme includes a
primitive predicate <code>null?</code>, which tests whether its argument is the empty
list.  The procedure <code>length</code>, which returns the number of items in a
list, illustrates this typical pattern of use:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">length items</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? items</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">0</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pln">length </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> items</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> odds
  </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">7</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">length odds</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">4</span></i>
</pre></div>

<p>The <code>length</code> procedure implements a simple recursive plan. The reduction
step is:
</p>
<ul>
<li> The <code>length</code> of any list is 1 plus the <code>length</code> of the <code>cdr</code> of
the list.

</li></ul>

<p>This is applied successively until we reach the base case:
</p>
<ul>
<li> The <code>length</code> of the empty list is 0.

</li></ul>

<p>We could also compute <code>length</code> in an iterative style:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">length items</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">length-iter a count</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? a</span><span class="clo">)</span><span class="pln">
        count
        </span><span class="opn">(</span><span class="pln">length-iter </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> a</span><span class="clo">)</span><span class="pln"> 
                     </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> count</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">length-iter items </span><span class="lit">0</span><span class="clo">))</span></pre></div>

<p>Another conventional programming technique is to “<code>cons</code> up” an answer
list while <code>cdr</code>ing down a list, as in the procedure <code>append</code>, which
takes two lists as arguments and combines their elements to make a new list:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">append squares odds</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">9</span><span class="pln"> </span><span class="lit">16</span><span class="pln"> </span><span class="lit">25</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">7</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">append odds squares</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">7</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">9</span><span class="pln"> </span><span class="lit">16</span><span class="pln"> </span><span class="lit">25</span><span class="clo">)</span></i>
</pre></div>

<p><code>Append</code> is also implemented using a recursive plan.  To <code>append</code>
lists <code>list1</code> and <code>list2</code>, do the following:
</p>
<ul>
<li> If <code>list1</code> is the empty list, then the result is just <code>list2</code>.

</li><li> Otherwise, <code>append</code> the <code>cdr</code> of <code>list1</code> and <code>list2</code>, and
<code>cons</code> the <code>car</code> of <code>list1</code> onto the result:

</li></ul>

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append list1 list2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? list1</span><span class="clo">)</span><span class="pln">
      list2
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> list1</span><span class="clo">)</span><span class="pln"> 
            </span><span class="opn">(</span><span class="pln">append </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> list1</span><span class="clo">)</span><span class="pln"> 
                    list2</span><span class="clo">))))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-2_002e17"></a>Exercise 2.17:</strong> Define a procedure
<code>last-pair</code> that returns the list that contains only the last element of a
given (nonempty) list:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">last-pair </span><span class="opn">(</span><span class="pln">list </span><span class="lit">23</span><span class="pln"> </span><span class="lit">72</span><span class="pln"> </span><span class="lit">149</span><span class="pln"> </span><span class="lit">34</span><span class="clo">))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">34</span><span class="clo">)</span></i>
</pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e18"></a>Exercise 2.18:</strong> Define a procedure <code>reverse</code>
that takes a list as argument and returns a list of the same elements in
reverse order:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">reverse </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">9</span><span class="pln"> </span><span class="lit">16</span><span class="pln"> </span><span class="lit">25</span><span class="clo">))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">25</span><span class="pln"> </span><span class="lit">16</span><span class="pln"> </span><span class="lit">9</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span></i>
</pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e19"></a>Exercise 2.19:</strong> Consider the change-counting
program of <a href="1_002e2.xhtml#g_t1_002e2_002e2">1.2.2</a>.  It would be nice to be able to easily change
the currency used by the program, so that we could compute the number of ways
to change a British pound, for example.  As the program is written, the
knowledge of the currency is distributed partly into the procedure
<code>first-denomination</code> and partly into the procedure <code>count-change</code>
(which knows that there are five kinds of U.S. coins).  It would be nicer to be
able to supply a list of coins to be used for making change.
</p>
<p>We want to rewrite the procedure <code>cc</code> so that its second argument is a
list of the values of the coins to use rather than an integer specifying which
coins to use.  We could then have lists that defined each kind of currency:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> us-coins 
  </span><span class="opn">(</span><span class="pln">list </span><span class="lit">50</span><span class="pln"> </span><span class="lit">25</span><span class="pln"> </span><span class="lit">10</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> uk-coins 
  </span><span class="opn">(</span><span class="pln">list </span><span class="lit">100</span><span class="pln"> </span><span class="lit">50</span><span class="pln"> </span><span class="lit">20</span><span class="pln"> </span><span class="lit">10</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0.5</span><span class="clo">))</span></pre></div>

<p>We could then call <code>cc</code> as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">cc </span><span class="lit">100</span><span class="pln"> us-coins</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">292</span></i>
</pre></div>

<p>To do this will require changing the program <code>cc</code> somewhat.  It will still
have the same form, but it will access its second argument differently, as
follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cc amount coin-values</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> amount </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> 
         </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> amount </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> 
             </span><span class="opn">(</span><span class="pln">no-more? coin-values</span><span class="clo">))</span><span class="pln"> 
         </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
         </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cc 
             amount
             </span><span class="opn">(</span><span class="pln">except-first-denomination 
              coin-values</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">cc 
             </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> amount
                </span><span class="opn">(</span><span class="pln">first-denomination 
                 coin-values</span><span class="clo">))</span><span class="pln">
             coin-values</span><span class="clo">)))))</span></pre></div>

<p>Define the procedures <code>first-denomination</code>,
<code>except-first-denomination</code> and <code>no-more?</code> in terms of primitive
operations on list structures.  Does the order of the list <code>coin-values</code>
affect the answer produced by <code>cc</code>?  Why or why not?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e20"></a>Exercise 2.20:</strong> The procedures <code>+</code>,
<code>*</code>, and <code>list</code> take arbitrary numbers of arguments. One way to
define such procedures is to use <code>define</code> with <a id="index-dotted_002dtail-notation"></a>
<em>dotted-tail notation</em>.  
In a procedure definition, a parameter list that has a dot before
the last parameter name indicates that, when the procedure is called, the
initial parameters (if any) will have as values the initial arguments, as
usual, but the final parameter’s value will be a <a id="index-list-2"></a>
<em>list</em> of any
remaining arguments.  For instance, given the definition
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f x y </span><span class="pun">.</span><span class="pln"> z</span><span class="clo">)</span><span class="pln"> ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>the procedure <code>f</code> can be called with two or more arguments.  If we
evaluate
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">f </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">6</span><span class="clo">)</span></pre></div>

<p>then in the body of <code>f</code>, <code>x</code> will be 1, <code>y</code> will be 2, and
<code>z</code> will be the list <code>(3 4 5 6)</code>.  Given the definition
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">g </span><span class="pun">.</span><span class="pln"> w</span><span class="clo">)</span><span class="pln"> ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>the procedure <code>g</code> can be called with zero or more arguments.  If we
evaluate
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">g </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">6</span><span class="clo">)</span></pre></div>

<p>then in the body of <code>g</code>, <code>w</code> will be the list <code>(1 2 3 4 5
6)</code>.<a class="footnote_link" id="DOCF77" href="#FOOT77"><sup>77</sup></a>
</p>
<p>Use this notation to write a procedure <code>same-parity</code> that takes one or
more integers and returns a list of all the arguments that have the same
even-odd parity as the first argument.  For example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">same-parity </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">6</span><span class="pln"> </span><span class="lit">7</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">7</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">same-parity </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">6</span><span class="pln"> </span><span class="lit">7</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">2</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">6</span><span class="clo">)</span></i>
</pre></div>
</blockquote>

<a id="Mapping-over-lists"></a>
<h5 class="subsubheading">Mapping over lists</h5>

<p>One extremely useful operation is to apply some transformation to each element
in a list and generate the list of results.  For instance, the following
procedure scales each number in a list by a given factor:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scale-list items factor</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? items</span><span class="clo">)</span><span class="pln">
      nil
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> items</span><span class="clo">)</span><span class="pln"> factor</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">scale-list </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> items</span><span class="clo">)</span><span class="pln"> 
                        factor</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">scale-list </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="clo">)</span><span class="pln"> </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">10</span><span class="pln"> </span><span class="lit">20</span><span class="pln"> </span><span class="lit">30</span><span class="pln"> </span><span class="lit">40</span><span class="pln"> </span><span class="lit">50</span><span class="clo">)</span></i>
</pre></div>

<p>We can abstract this general idea and capture it as a common pattern expressed
as a higher-order procedure, just as in <a href="1_002e3.xhtml#g_t1_002e3">1.3</a>.  The higher-order
procedure here is called <code>map</code>.  <code>Map</code> takes as arguments a procedure
of one argument and a list, and returns a list of the results produced by
applying the procedure to each element in the list:<a class="footnote_link" id="DOCF78" href="#FOOT78"><sup>78</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">map proc items</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? items</span><span class="clo">)</span><span class="pln">
      nil
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">proc </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> items</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">map proc </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> items</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">map abs </span><span class="opn">(</span><span class="pln">list </span><span class="lit">-10</span><span class="pln"> </span><span class="lit">2.5</span><span class="pln"> </span><span class="lit">-11.6</span><span class="pln"> </span><span class="lit">17</span><span class="clo">))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">10</span><span class="pln"> </span><span class="lit">2.5</span><span class="pln"> </span><span class="lit">11.6</span><span class="pln"> </span><span class="lit">17</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x</span><span class="clo">))</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">9</span><span class="pln"> </span><span class="lit">16</span><span class="clo">)</span></i>
</pre></div>

<p>Now we can give a new definition of <code>scale-list</code> in terms of <code>map</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scale-list items factor</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x factor</span><span class="clo">))</span><span class="pln">
       items</span><span class="clo">))</span></pre></div>

<p><code>Map</code> is an important construct, not only because it captures a common
pattern, but because it establishes a higher level of abstraction in dealing
with lists.  In the original definition of <code>scale-list</code>, the recursive
structure of the program draws attention to the element-by-element processing
of the list.  Defining <code>scale-list</code> in terms of <code>map</code> suppresses that
level of detail and emphasizes that scaling transforms a list of elements to a
list of results.  The difference between the two definitions is not that the
computer is performing a different process (it isn’t) but that we think about
the process differently.  In effect, <code>map</code> helps establish an abstraction
barrier that isolates the implementation of procedures that transform lists
from the details of how the elements of the list are extracted and combined.
Like the barriers shown in <a href="2_002e1.xhtml#Figure-2_002e1">Figure 2.1</a>, this abstraction gives us the
flexibility to change the low-level details of how sequences are implemented,
while preserving the conceptual framework of operations that transform
sequences to sequences.  Section <a href="#g_t2_002e2_002e3">2.2.3</a> expands on this use of sequences
as a framework for organizing programs.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e21"></a>Exercise 2.21:</strong> The procedure <code>square-list</code>
takes a list of numbers as argument and returns a list of the squares of those
numbers.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">square-list </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">9</span><span class="pln"> </span><span class="lit">16</span><span class="clo">)</span></i>
</pre></div>

<p>Here are two different definitions of <code>square-list</code>.  Complete both of
them by filling in the missing expressions:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square-list items</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? items</span><span class="clo">)</span><span class="pln">
      nil
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square-list items</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">map ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e22"></a>Exercise 2.22:</strong> Louis Reasoner tries to rewrite
the first <code>square-list</code> procedure of <a href="#Exercise-2_002e21">Exercise 2.21</a> so that it
evolves an iterative process:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square-list items</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter things answer</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? things</span><span class="clo">)</span><span class="pln">
        answer
        </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> things</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> things</span><span class="clo">))</span><span class="pln">
                    answer</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">iter items nil</span><span class="clo">))</span></pre></div>

<p>Unfortunately, defining <code>square-list</code> this way produces the answer list in
the reverse order of the one desired.  Why?
</p>
<p>Louis then tries to fix his bug by interchanging the arguments to <code>cons</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square-list items</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter things answer</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? things</span><span class="clo">)</span><span class="pln">
        answer
        </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> things</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> answer
                    </span><span class="opn">(</span><span class="pln">square 
                     </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> things</span><span class="clo">))))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">iter items nil</span><span class="clo">))</span></pre></div>

<p>This doesn’t work either.  Explain.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e23"></a>Exercise 2.23:</strong> The procedure <code>for-each</code> is
similar to <code>map</code>.  It takes as arguments a procedure and a list of
elements.  However, rather than forming a list of the results, <code>for-each</code>
just applies the procedure to each of the elements in turn, from left to right.
The values returned by applying the procedure to the elements are not used at
all—<code>for-each</code> is used with procedures that perform an action, such as
printing.  For example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">for-each 
 </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">display x</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">list </span><span class="lit">57</span><span class="pln"> </span><span class="lit">321</span><span class="pln"> </span><span class="lit">88</span><span class="clo">))</span><span class="pln">

</span><i><span class="lit">57</span></i><span class="pln">
</span><i><span class="lit">321</span></i><span class="pln">
</span><i><span class="lit">88</span></i>
</pre></div>

<p>The value returned by the call to <code>for-each</code> (not illustrated above) can
be something arbitrary, such as true.  Give an implementation of
<code>for-each</code>.
</p></blockquote>

<a id="g_t2_002e2_002e2"></a>
<a id="Hierarchical-Structures"></a>
<h4 class="subsection"><span class="secnum">2.2.2</span><span class="sectitle">Hierarchical Structures</span></h4>

<p>The representation of sequences in terms of lists generalizes naturally to
represent sequences whose elements may themselves be sequences.  For example,
we can regard the object <code>((1 2) 3 4)</code> constructed by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">))</span></pre></div>

<p>as a list of three items, the first of which is itself a list, <code>(1 2)</code>.
Indeed, this is suggested by the form in which the result is printed by the
interpreter.  <a href="#Figure-2_002e5">Figure 2.5</a> shows the representation of
this structure in terms of pairs.
</p>
<figure class="float">
<a id="Figure-2_002e5"></a>
<object style="width: 51.89ex; height: 25.73ex;" data="fig/chap2/Fig2.5e.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.5:</strong> Structure formed by <code>(cons (list 1 2) (list 3 4))</code>.</p>
</figcaption>
</figure>

<p>Another way to think of sequences whose elements are sequences is as
<a id="index-trees"></a>
<em>trees</em>.  The elements of the sequence are the branches of the tree,
and elements that are themselves sequences are subtrees.  <a href="#Figure-2_002e6">Figure 2.6</a>
shows the structure in <a href="#Figure-2_002e5">Figure 2.5</a> viewed as a tree.
</p>
<figure class="float">
<a id="Figure-2_002e6"></a>
<object style="width: 15.02ex; height: 17.01ex;" data="fig/chap2/Fig2.6b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.6:</strong> The list structure in <a href="#Figure-2_002e5">Figure 2.5</a> viewed as a tree.</p>
</figcaption>
</figure>

<p>Recursion is a natural tool for dealing with tree structures, since we can
often reduce operations on trees to operations on their branches, which reduce
in turn to operations on the branches of the branches, and so on, until we
reach the leaves of the tree.  As an example, compare the <code>length</code>
procedure of <a href="#g_t2_002e2_002e1">2.2.1</a> with the <code>count-leaves</code> procedure, which
returns the total number of leaves of a tree:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)))</span></pre></div>

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">length x</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">3</span></i>
</pre></div>

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">count-leaves x</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">4</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">list x x</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(((</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span><span class="pln"> </span><span class="opn">((</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">))</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">length </span><span class="opn">(</span><span class="pln">list x x</span><span class="clo">))</span><span class="pln">
</span><i><span class="lit">2</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">count-leaves </span><span class="opn">(</span><span class="pln">list x x</span><span class="clo">))</span><span class="pln">
</span><i><span class="lit">8</span></i>
</pre></div>

<p>To implement <code>count-leaves</code>, recall the recursive plan for computing
<code>length</code>:
</p>
<ul>
<li> <code>Length</code> of a list <code>x</code> is 1 plus <code>length</code> of the
<code>cdr</code> of <code>x</code>.

</li><li> <code>Length</code> of the empty list is 0.

</li></ul>

<p><code>Count-leaves</code> is similar.  The value for the empty list is the same:
</p>
<ul>
<li> <code>Count-leaves</code> of the empty list is 0.

</li></ul>

<p>But in the reduction step, where we strip off the <code>car</code> of the list, we
must take into account that the <code>car</code> may itself be a tree whose leaves we
need to count.  Thus, the appropriate reduction step is
</p>
<ul>
<li> <code>Count-leaves</code> of a tree <code>x</code> is <code>count-leaves</code> of the <code>car</code>
of <code>x</code> plus <code>count-leaves</code> of the <code>cdr</code> of <code>x</code>.

</li></ul>

<p>Finally, by taking <code>car</code>s we reach actual leaves, so we need another base
case:
</p>
<ul>
<li> <code>Count-leaves</code> of a leaf is 1.

</li></ul>

<p>To aid in writing recursive procedures on trees, Scheme provides the primitive
predicate <code>pair?</code>, which tests whether its argument is a pair.  Here is
the complete procedure:<a class="footnote_link" id="DOCF79" href="#FOOT79"><sup>79</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">count-leaves x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? x</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">not </span><span class="opn">(</span><span class="pln">pair? x</span><span class="clo">))</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">count-leaves </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">count-leaves </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> x</span><span class="clo">))))))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-2_002e24"></a>Exercise 2.24:</strong> Suppose we evaluate the
expression <code>(list 1 (list 2 (list 3 4)))</code>.  Give the result printed by the
interpreter, the corresponding box-and-pointer structure, and the
interpretation of this as a tree (as in <a href="#Figure-2_002e6">Figure 2.6</a>).
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e25"></a>Exercise 2.25:</strong> Give combinations of <code>car</code>s
and <code>cdr</code>s that will pick 7 from each of the following lists:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="opn">(</span><span class="lit">5</span><span class="pln"> </span><span class="lit">7</span><span class="clo">)</span><span class="pln"> </span><span class="lit">9</span><span class="clo">)</span><span class="pln">
</span><span class="opn">((</span><span class="lit">7</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="lit">2</span><span class="pln"> </span><span class="opn">(</span><span class="lit">3</span><span class="pln"> </span><span class="opn">(</span><span class="lit">4</span><span class="pln"> </span><span class="opn">(</span><span class="lit">5</span><span class="pln"> </span><span class="opn">(</span><span class="lit">6</span><span class="pln"> </span><span class="lit">7</span><span class="clo">))))))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e26"></a>Exercise 2.26:</strong> Suppose we define <code>x</code> and
<code>y</code> to be two lists:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> y </span><span class="opn">(</span><span class="pln">list </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">6</span><span class="clo">))</span></pre></div>

<p>What result is printed by the interpreter in response to evaluating each of the
following expressions:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">append x y</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> x y</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">list x y</span><span class="clo">)</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e27"></a>Exercise 2.27:</strong> Modify your <code>reverse</code>
procedure of <a href="#Exercise-2_002e18">Exercise 2.18</a> to produce a <code>deep-reverse</code> procedure
that takes a list as argument and returns as its value the list with its
elements reversed and with all sublists deep-reversed as well.  For example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x 
  </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)))</span><span class="pln">

x
</span><i><span class="opn">((</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">))</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">reverse x</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">((</span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="clo">))</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">deep-reverse x</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">((</span><span class="lit">4</span><span class="pln"> </span><span class="lit">3</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">2</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))</span></i>
</pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e28"></a>Exercise 2.28:</strong> Write a procedure <code>fringe</code>
that takes as argument a tree (represented as a list) and returns a list whose
elements are all the leaves of the tree arranged in left-to-right order.  For
example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x 
  </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">fringe x</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">fringe </span><span class="opn">(</span><span class="pln">list x x</span><span class="clo">))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span></i>
</pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e29"></a>Exercise 2.29:</strong> A binary mobile consists of two
branches, a left branch and a right branch.  Each branch is a rod of a certain
length, from which hangs either a weight or another binary mobile.  We can
represent a binary mobile using compound data by constructing it from two
branches (for example, using <code>list</code>):
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-mobile left right</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">list left right</span><span class="clo">))</span></pre></div>

<p>A branch is constructed from a <code>length</code> (which must be a number) together
with a <code>structure</code>, which may be either a number (representing a simple
weight) or another mobile:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-branch length structure</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">list length structure</span><span class="clo">))</span></pre></div>

<ol>
<li> Write the corresponding selectors <code>left-branch</code> and <code>right-branch</code>,
which return the branches of a mobile, and <code>branch-length</code> and
<code>branch-structure</code>, which return the components of a branch.

</li><li> Using your selectors, define a procedure <code>total-weight</code> that returns the
total weight of a mobile.

</li><li> A mobile is said to be <a id="index-balanced"></a>
<em>balanced</em> if the torque applied by its top-left
branch is equal to that applied by its top-right branch (that is, if the length
of the left rod multiplied by the weight hanging from that rod is equal to the
corresponding product for the right side) and if each of the submobiles hanging
off its branches is balanced. Design a predicate that tests whether a binary
mobile is balanced.

</li><li> Suppose we change the representation of mobiles so that the constructors are

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-mobile left right</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> left right</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-branch length structure</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> length structure</span><span class="clo">))</span></pre></div>

<p>How much do you need to change your programs to convert to the new
representation?
</p>
</li></ol>
</blockquote>

<a id="Mapping-over-trees"></a>
<h5 class="subsubheading">Mapping over trees</h5>

<p>Just as <code>map</code> is a powerful abstraction for dealing with sequences,
<code>map</code> together with recursion is a powerful abstraction for dealing with
trees.  For instance, the <code>scale-tree</code> procedure, analogous to
<code>scale-list</code> of <a href="#g_t2_002e2_002e1">2.2.1</a>, takes as arguments a numeric factor
and a tree whose leaves are numbers.  It returns a tree of the same shape,
where each number is multiplied by the factor.  The recursive plan for
<code>scale-tree</code> is similar to the one for <code>count-leaves</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scale-tree tree factor</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? tree</span><span class="clo">)</span><span class="pln"> nil</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">not </span><span class="opn">(</span><span class="pln">pair? tree</span><span class="clo">))</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> tree factor</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scale-tree </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> tree</span><span class="clo">)</span><span class="pln"> 
                           factor</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">scale-tree </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> tree</span><span class="clo">)</span><span class="pln"> 
                           factor</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">scale-tree </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> 
                  </span><span class="opn">(</span><span class="pln">list </span><span class="lit">2</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span><span class="pln"> </span><span class="lit">5</span><span class="clo">)</span><span class="pln"> 
                  </span><span class="opn">(</span><span class="pln">list </span><span class="lit">6</span><span class="pln"> </span><span class="lit">7</span><span class="clo">))</span><span class="pln">
            </span><span class="lit">10</span><span class="clo">)</span><span class="pln">

</span><i><span class="opn">(</span><span class="lit">10</span><span class="pln"> </span><span class="opn">(</span><span class="lit">20</span><span class="pln"> </span><span class="opn">(</span><span class="lit">30</span><span class="pln"> </span><span class="lit">40</span><span class="clo">)</span><span class="pln"> </span><span class="lit">50</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">60</span><span class="pln"> </span><span class="lit">70</span><span class="clo">))</span></i>
</pre></div>

<p>Another way to implement <code>scale-tree</code> is to regard the tree as a sequence
of sub-trees and use <code>map</code>.  We map over the sequence, scaling each
sub-tree in turn, and return the list of results.  In the base case, where the
tree is a leaf, we simply multiply by the factor:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scale-tree tree factor</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sub-tree</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pair? sub-tree</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">scale-tree sub-tree factor</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> sub-tree factor</span><span class="clo">)))</span><span class="pln">
       tree</span><span class="clo">))</span></pre></div>

<p>Many tree operations can be implemented by similar combinations of sequence
operations and recursion.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e30"></a>Exercise 2.30:</strong> Define a procedure
<code>square-tree</code> analogous to the <code>square-list</code> procedure of
<a href="#Exercise-2_002e21">Exercise 2.21</a>.  That is, <code>square-tree</code> should behave as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">square-tree
 </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">list </span><span class="lit">2</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span><span class="pln"> </span><span class="lit">5</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">list </span><span class="lit">6</span><span class="pln"> </span><span class="lit">7</span><span class="clo">)))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="lit">4</span><span class="pln"> </span><span class="opn">(</span><span class="lit">9</span><span class="pln"> </span><span class="lit">16</span><span class="clo">)</span><span class="pln"> </span><span class="lit">25</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">36</span><span class="pln"> </span><span class="lit">49</span><span class="clo">))</span></i>
</pre></div>

<p>Define <code>square-tree</code> both directly (i.e., without using any higher-order
procedures) and also by using <code>map</code> and recursion.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e31"></a>Exercise 2.31:</strong> Abstract your answer to
<a href="#Exercise-2_002e30">Exercise 2.30</a> to produce a procedure <code>tree-map</code> with the property
that <code>square-tree</code> could be defined as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square-tree tree</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">tree-map square tree</span><span class="clo">))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e32"></a>Exercise 2.32:</strong> We can represent a set as a list
of distinct elements, and we can represent the set of all subsets of the set as
a list of lists.  For example, if the set is <code>(1 2 3)</code>, then the set of
all subsets is <code>(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))</code>.  Complete the
following definition of a procedure that generates the set of subsets of a set
and give a clear explanation of why it works:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">subsets s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? s</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">list nil</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">rest </span><span class="opn">(</span><span class="pln">subsets </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> s</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">append rest </span><span class="opn">(</span><span class="pln">map ⟨</span><span class="pun">??</span><span class="pln">⟩ rest</span><span class="clo">)))))</span></pre></div>
</blockquote>

<a id="g_t2_002e2_002e3"></a>
<a id="Sequences-as-Conventional-Interfaces"></a>
<h4 class="subsection"><span class="secnum">2.2.3</span><span class="sectitle">Sequences as Conventional Interfaces</span></h4>

<p>In working with compound data, we’ve stressed how data abstraction permits us
to design programs without becoming enmeshed in the details of data
representations, and how abstraction preserves for us the flexibility to
experiment with alternative representations.  In this section, we introduce
another powerful design principle for working with data structures—the use of
<a id="index-conventional-interfaces-1"></a>
<em>conventional interfaces</em>.
</p>
<p>In <a href="1_002e3.xhtml#g_t1_002e3">1.3</a> we saw how program abstractions, implemented as
higher-order procedures, can capture common patterns in programs that deal with
numerical data.  Our ability to formulate analogous operations for working with
compound data depends crucially on the style in which we manipulate our data
structures.  Consider, for example, the following procedure, analogous to the
<code>count-leaves</code> procedure of <a href="#g_t2_002e2_002e2">2.2.2</a>, which takes a tree as
argument and computes the sum of the squares of the leaves that are odd:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum-odd-squares tree</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? tree</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">not </span><span class="opn">(</span><span class="pln">pair? tree</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">odd? tree</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square tree</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum-odd-squares 
                  </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> tree</span><span class="clo">))</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">sum-odd-squares 
                  </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> tree</span><span class="clo">))))))</span></pre></div>

<p>On the surface, this procedure is very different from the following one, which
constructs a list of all the even Fibonacci numbers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>k</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, where
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math> is less than or equal to a given integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">even-fibs n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">next k</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> k n</span><span class="clo">)</span><span class="pln">
        nil
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">f </span><span class="opn">(</span><span class="pln">fib k</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">even? f</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> f </span><span class="opn">(</span><span class="pln">next </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> k </span><span class="lit">1</span><span class="clo">)))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">next </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> k </span><span class="lit">1</span><span class="clo">))))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">next </span><span class="lit">0</span><span class="clo">))</span></pre></div>

<p>Despite the fact that these two procedures are structurally very different, a
more abstract description of the two computations reveals a great deal of
similarity.  The first program
</p>
<ul>
<li> enumerates the leaves of a tree;

</li><li> filters them, selecting the odd ones;

</li><li> squares each of the selected ones; and

</li><li> accumulates the results using <code>+</code>, starting with 0.

</li></ul>

<p>The second program
</p>
<ul>
<li> enumerates the integers from 0 to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>;

</li><li> computes the Fibonacci number for each integer;

</li><li> filters them, selecting the even ones; and

</li><li> accumulates the results using <code>cons</code>,  starting with the
empty list.

</li></ul>

<p>A signal-processing engineer would find it natural to conceptualize these
processes in terms of signals flowing through a cascade of stages, each of
which implements part of the program plan, as shown in <a href="#Figure-2_002e7">Figure 2.7</a>.  In
<code>sum-odd-squares</code>, we begin with an <a id="index-enumerator"></a>
<em>enumerator</em>, which generates
a “signal” consisting of the leaves of a given tree.  This signal is passed
through a <a id="index-filter-1"></a>
<em>filter</em>, which eliminates all but the odd elements.  The
resulting signal is in turn passed through a <a id="index-map"></a>
<em>map</em>, which is a
“transducer” that applies the <code>square</code> procedure to each element.  The
output of the map is then fed to an <a id="index-accumulator"></a>
<em>accumulator</em>, which combines the
elements using <code>+</code>, starting from an initial 0.  The plan for
<code>even-fibs</code> is analogous.
</p>
<figure class="float">
<a id="Figure-2_002e7"></a>
<object style="width: 57.93ex; height: 16.23ex;" data="fig/chap2/Fig2.7e.std.svg" type="image/svg+xml">SVG</object> 

<figcaption class="float-caption">
<p><strong>Figure 2.7:</strong> The signal-flow plans for the procedures <code>sum-odd-squares</code> (top) and <code>even-fibs</code> (bottom) reveal the commonality between the two programs.</p>
</figcaption>
</figure>

<p>Unfortunately, the two procedure definitions above fail to exhibit this
signal-flow structure.  For instance, if we examine the <code>sum-odd-squares</code>
procedure, we find that the enumeration is implemented partly by the
<code>null?</code> and <code>pair?</code> tests and partly by the tree-recursive structure
of the procedure.  Similarly, the accumulation is found partly in the tests and
partly in the addition used in the recursion.  In general, there are no
distinct parts of either procedure that correspond to the elements in the
signal-flow description.  Our two procedures decompose the computations in a
different way, spreading the enumeration over the program and mingling it with
the map, the filter, and the accumulation.  If we could organize our programs
to make the signal-flow structure manifest in the procedures we write, this
would increase the conceptual clarity of the resulting code.
</p>
<a id="Sequence-Operations"></a>
<h5 class="subsubheading">Sequence Operations</h5>

<p>The key to organizing programs so as to more clearly reflect the signal-flow
structure is to concentrate on the “signals” that flow from one stage in the
process to the next.  If we represent these signals as lists, then we can use
list operations to implement the processing at each of the stages.  For
instance, we can implement the mapping stages of the signal-flow diagrams using
the <code>map</code> procedure from <a href="#g_t2_002e2_002e1">2.2.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">map square </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="clo">))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">9</span><span class="pln"> </span><span class="lit">16</span><span class="pln"> </span><span class="lit">25</span><span class="clo">)</span></i>
</pre></div>

<p>Filtering a sequence to select only those elements that satisfy a given
predicate is accomplished by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">filter predicate sequence</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? sequence</span><span class="clo">)</span><span class="pln"> nil</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">predicate </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> sequence</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> sequence</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">filter predicate 
                       </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> sequence</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">  </span><span class="opn">(</span><span class="pln">filter predicate 
                       </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> sequence</span><span class="clo">)))))</span></pre></div>

<p>For example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">filter odd? </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="clo">))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">5</span><span class="clo">)</span></i>
</pre></div>

<p>Accumulations can be implemented by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">accumulate op initial sequence</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? sequence</span><span class="clo">)</span><span class="pln">
      initial
      </span><span class="opn">(</span><span class="pln">op </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> sequence</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">accumulate op 
                      initial 
                      </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> sequence</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">accumulate </span><span class="pun">+</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="clo">))</span><span class="pln">
</span><i><span class="lit">15</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">accumulate </span><span class="pun">*</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="clo">))</span><span class="pln">
</span><i><span class="lit">120</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">accumulate </span><span class="kwd">cons</span><span class="pln"> nil </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="clo">))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="clo">)</span></i>
</pre></div>

<p>All that remains to implement signal-flow diagrams is to enumerate the sequence
of elements to be processed.  For <code>even-fibs</code>, we need to generate the
sequence of integers in a given range, which we can do as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">enumerate-interval low high</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> low high</span><span class="clo">)</span><span class="pln">
      nil
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> low 
            </span><span class="opn">(</span><span class="pln">enumerate-interval 
             </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> low </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> 
             high</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">enumerate-interval </span><span class="lit">2</span><span class="pln"> </span><span class="lit">7</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">6</span><span class="pln"> </span><span class="lit">7</span><span class="clo">)</span></i>
</pre></div>

<p>To enumerate the leaves of a tree, we can use<a class="footnote_link" id="DOCF80" href="#FOOT80"><sup>80</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">enumerate-tree tree</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? tree</span><span class="clo">)</span><span class="pln"> nil</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">not </span><span class="opn">(</span><span class="pln">pair? tree</span><span class="clo">))</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list tree</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append 
               </span><span class="opn">(</span><span class="pln">enumerate-tree </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> tree</span><span class="clo">))</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">enumerate-tree </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> tree</span><span class="clo">))))))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">enumerate-tree </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">2</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">))</span><span class="pln"> </span><span class="lit">5</span><span class="clo">))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="clo">)</span></i>
</pre></div>

<p>Now we can reformulate <code>sum-odd-squares</code> and <code>even-fibs</code> as in the
signal-flow diagrams.  For <code>sum-odd-squares</code>, we enumerate the sequence of
leaves of the tree, filter this to keep only the odd numbers in the sequence,
square each element, and sum the results:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum-odd-squares tree</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate 
   </span><span class="pun">+</span><span class="pln">
   </span><span class="lit">0</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">map square
        </span><span class="opn">(</span><span class="pln">filter odd?
                </span><span class="opn">(</span><span class="pln">enumerate-tree tree</span><span class="clo">)))))</span></pre></div>

<p>For <code>even-fibs</code>, we enumerate the integers from 0 to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, generate the
Fibonacci number for each of these integers, filter the resulting sequence to
keep only the even elements, and accumulate the results into a list:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">even-fibs n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate 
   </span><span class="kwd">cons</span><span class="pln">
   nil
   </span><span class="opn">(</span><span class="pln">filter even?
           </span><span class="opn">(</span><span class="pln">map fib
                </span><span class="opn">(</span><span class="pln">enumerate-interval </span><span class="lit">0</span><span class="pln"> n</span><span class="clo">)))))</span></pre></div>

<p>The value of expressing programs as sequence operations is that this helps us
make program designs that are modular, that is, designs that are constructed by
combining relatively independent pieces.  We can encourage modular design by
providing a library of standard components together with a conventional
interface for connecting the components in flexible ways.
</p>
<p>Modular construction is a powerful strategy for controlling complexity in
engineering design.  In real signal-processing applications, for example,
designers regularly build systems by cascading elements selected from
standardized families of filters and transducers.  Similarly, sequence
operations provide a library of standard program elements that we can mix and
match.  For instance, we can reuse pieces from the <code>sum-odd-squares</code> and
<code>even-fibs</code> procedures in a program that constructs a list of the squares
of the first <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>+</mo>
    <mn>1</mn>
  </mrow>
</math> Fibonacci numbers:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list-fib-squares n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate 
   </span><span class="kwd">cons</span><span class="pln">
   nil
   </span><span class="opn">(</span><span class="pln">map square
        </span><span class="opn">(</span><span class="pln">map fib
             </span><span class="opn">(</span><span class="pln">enumerate-interval </span><span class="lit">0</span><span class="pln"> n</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">list-fib-squares </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">9</span><span class="pln"> </span><span class="lit">25</span><span class="pln"> </span><span class="lit">64</span><span class="pln"> </span><span class="lit">169</span><span class="pln"> </span><span class="lit">441</span><span class="pln"> </span><span class="lit">1156</span><span class="pln"> </span><span class="lit">3025</span><span class="clo">)</span></i>
</pre></div>

<p>We can rearrange the pieces and use them in computing the product of the squares of the odd
integers in a sequence:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">product-of-squares-of-odd-elements
   sequence</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate 
   </span><span class="pun">*</span><span class="pln">
   </span><span class="lit">1</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">map square </span><span class="opn">(</span><span class="pln">filter odd? sequence</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">product-of-squares-of-odd-elements 
 </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="clo">))</span><span class="pln">
</span><i><span class="lit">225</span></i>
</pre></div>

<p>We can also formulate conventional data-processing applications in terms of
sequence operations.  Suppose we have a sequence of personnel records and we
want to find the salary of the highest-paid programmer.  Assume that we have a
selector <code>salary</code> that returns the salary of a record, and a predicate
<code>programmer?</code> that tests if a record is for a programmer.  Then we can
write
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">salary-of-highest-paid-programmer
   records</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate 
   max
   </span><span class="lit">0</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">map salary
        </span><span class="opn">(</span><span class="pln">filter programmer? records</span><span class="clo">))))</span></pre></div>

<p>These examples give just a hint of the vast range of operations that can be
expressed as sequence operations.<a class="footnote_link" id="DOCF81" href="#FOOT81"><sup>81</sup></a>
</p>
<p>Sequences, implemented here as lists, serve as a conventional interface that
permits us to combine processing modules.  Additionally, when we uniformly
represent structures as sequences, we have localized the data-structure
dependencies in our programs to a small number of sequence operations.  By
changing these, we can experiment with alternative representations of
sequences, while leaving the overall design of our programs intact.  We will
exploit this capability in <a href="3_002e5.xhtml#g_t3_002e5">3.5</a>, when we generalize the
sequence-processing paradigm to admit infinite sequences.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e33"></a>Exercise 2.33:</strong> Fill in the missing expressions
to complete the following definitions of some basic list-manipulation
operations as accumulations:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">map p sequence</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> 
              nil sequence</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append seq1 seq2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate </span><span class="kwd">cons</span><span class="pln"> ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">length sequence</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate ⟨</span><span class="pun">??</span><span class="pln">⟩ </span><span class="lit">0</span><span class="pln"> sequence</span><span class="clo">))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e34"></a>Exercise 2.34:</strong> Evaluating a polynomial in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>
at a given value of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> can be formulated as an accumulation.  We evaluate
the polynomial
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mi>n</mi>
    </msub>
    <msup>
      <mi>x</mi>
      <mi>n</mi>
    </msup>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>n</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <msup>
      <mi>x</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>n</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msup>
  </mrow>
  <mo>+</mo>
  <mo>⋯<!-- ⋯ --></mo>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mn>1</mn>
    </msub>
    <mi>x</mi>
  </mrow>
  <mo>+</mo>
  <msub>
    <mi>a</mi>
    <mn>0</mn>
  </msub>
</math>
using a well-known algorithm called <a id="index-Horner_0027s-rule"></a>
<em>Horner’s rule</em>, which structures
the computation as
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mo>…<!-- … --></mo>
    <mo stretchy="false">(</mo>
    <msub>
      <mi>a</mi>
      <mi>n</mi>
    </msub>
    <mi>x</mi>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>n</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <mo stretchy="false">)</mo>
    <mi>x</mi>
  </mrow>
  <mo>+</mo>
  <mo>⋯<!-- ⋯ --></mo>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mn>1</mn>
    </msub>
    <mo stretchy="false">)</mo>
    <mi>x</mi>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mn>0</mn>
    </msub>
    <mo>.</mo>
  </mrow>
</math>
In other words, we start with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mi>n</mi>
  </msub>
</math>, multiply by <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>, add
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>n</mi>
      <mo>−<!-- − --></mo>
      <mn>1</mn>
    </mrow>
  </msub>
</math>, multiply by <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>, and so on, until we reach
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mn>0</mn>
  </msub>
</math>.<a class="footnote_link" id="DOCF82" href="#FOOT82"><sup>82</sup></a>
</p>
<p>Fill in the following template to produce a procedure that evaluates a
polynomial using Horner’s rule.  Assume that the coefficients of the polynomial
are arranged in a sequence, from <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mn>0</mn>
  </msub>
</math> through <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mi>n</mi>
  </msub>
</math>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">horner-eval x coefficient-sequence</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate 
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">this-coeff higher-terms</span><span class="clo">)</span><span class="pln">
     ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
   </span><span class="lit">0</span><span class="pln">
   coefficient-sequence</span><span class="clo">))</span></pre></div>

<p>For example, to compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mo>+</mo>
    <mn>3</mn>
    <mi>x</mi>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>5</mn>
    <msup>
      <mi>x</mi>
      <mn>3</mn>
    </msup>
    <mo>+</mo>
    <msup>
      <mi>x</mi>
      <mn>5</mn>
    </msup>
  </mrow>
</math> at <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo>=</mo>
    <mn>2</mn>
  </mrow>
</math> you
would evaluate
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">horner-eval </span><span class="lit">2</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e35"></a>Exercise 2.35:</strong> Redefine <code>count-leaves</code> from
<a href="#g_t2_002e2_002e2">2.2.2</a> as an accumulation:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">count-leaves t</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩ </span><span class="opn">(</span><span class="pln">map ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">)))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e36"></a>Exercise 2.36:</strong> The procedure <code>accumulate-n</code>
is similar to <code>accumulate</code> except that it takes as its third argument a
sequence of sequences, which are all assumed to have the same number of
elements.  It applies the designated accumulation procedure to combine all the
first elements of the sequences, all the second elements of the sequences, and
so on, and returns a sequence of the results.  For instance, if <code>s</code> is a
sequence containing four sequences, <code>((1 2 3) (4 5 6) (7 8 9) (10 11
12)),</code> then the value of <code>(accumulate-n + 0 s)</code> should be the sequence
<code>(22 26 30)</code>.  Fill in the missing expressions in the following definition
of <code>accumulate-n</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">accumulate-n op init seqs</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> seqs</span><span class="clo">))</span><span class="pln">
      nil
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">accumulate op init ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">accumulate-n op init ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">))))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e37"></a>Exercise 2.37:</strong>
Suppose we represent vectors <b>v</b> = <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mo stretchy="false">(</mo>
  <msub>
    <mi>v</mi>
    <mi>i</mi>
  </msub>
  <mo stretchy="false">)</mo>
</mrow>
</math> as sequences of numbers, and
matrices <b>m</b> = <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
  <mo stretchy="false">(</mo>
  <msub>
    <mi>m</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>i</mi>
      <mi>j</mi>
    </mrow>
  </msub>
  <mo stretchy="false">)</mo>
</mrow>
</math> as sequences of vectors (the rows of the
matrix).  For example, the matrix
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mo>(</mo>
    <mtable rowspacing="4pt" columnspacing="1em">
      <mtr>
        <mtd>
          <mn>1</mn>
        </mtd>
        <mtd>
          <mn>2</mn>
        </mtd>
        <mtd>
          <mn>3</mn>
        </mtd>
        <mtd>
          <mn>4</mn>
        </mtd>
      </mtr>
      <mtr>
        <mtd>
          <mn>4</mn>
        </mtd>
        <mtd>
          <mn>5</mn>
        </mtd>
        <mtd>
          <mn>6</mn>
        </mtd>
        <mtd>
          <mn>6</mn>
        </mtd>
      </mtr>
      <mtr>
        <mtd>
          <mn>6</mn>
        </mtd>
        <mtd>
          <mn>7</mn>
        </mtd>
        <mtd>
          <mn>8</mn>
        </mtd>
        <mtd>
          <mn>9</mn>
        </mtd>
      </mtr>
    </mtable>
    <mo>)</mo>
  </mrow>
</math>
is represented as the sequence <code>((1 2 3 4) (4 5 6 6) (6 7 8 9))</code>.  With
this representation, we can use sequence operations to concisely express the
basic matrix and vector operations.  These operations (which are described in
any book on matrix algebra) are the following:
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mtable columnalign="right left" rowspacing=".5em" columnspacing="thickmathspace">
  <mtr>
    <mtd>
      <mtext>(dot-product v w)</mtext>
    </mtd>
    <mtd>
      <mtext>returns the sum</mtext>
      <mspace width="thickmathspace"/>
      <msub>
        <mi mathvariant="normal">Σ<!-- Σ --></mi>
        <mi>i</mi>
      </msub>
      <msub>
        <mi>v</mi>
        <mi>i</mi>
      </msub>
      <msub>
        <mi>w</mi>
        <mi>i</mi>
      </msub>
      <mo>;</mo>
    </mtd>
  </mtr>
  <mtr>
    <mtd>
      <mtext>(matrix-*-vector m v)</mtext>
    </mtd>
    <mtd>
      <mtext>returns the vector</mtext>
      <mspace width="thickmathspace"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi mathvariant="bold">t</mi>
      </mrow>
      <mo>,</mo>
    </mtd>
  </mtr>
  <mtr>
    <mtd/>
    <mtd>
      <mtext>where</mtext>
      <mspace width="thickmathspace"/>
      <msub>
        <mi>t</mi>
        <mi>i</mi>
      </msub>
      <mo>=</mo>
      <msub>
        <mi mathvariant="normal">Σ<!-- Σ --></mi>
        <mi>j</mi>
      </msub>
      <msub>
        <mi>m</mi>
        <mrow class="MJX-TeXAtom-ORD">
          <mi>i</mi>
          <mi>j</mi>
        </mrow>
      </msub>
      <msub>
        <mi>v</mi>
        <mi>j</mi>
      </msub>
      <mo>;</mo>
    </mtd>
  </mtr>
  <mtr>
    <mtd>
      <mtext>(matrix-*-matrix m n)</mtext>
    </mtd>
    <mtd>
      <mtext>returns the matrix</mtext>
      <mspace width="thickmathspace"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi mathvariant="bold">p</mi>
      </mrow>
      <mo>,</mo>
    </mtd>
  </mtr>
  <mtr>
    <mtd/>
    <mtd>
      <mtext>where</mtext>
      <mspace width="thickmathspace"/>
      <msub>
        <mi>p</mi>
        <mrow class="MJX-TeXAtom-ORD">
          <mi>i</mi>
          <mi>j</mi>
        </mrow>
      </msub>
      <mo>=</mo>
      <msub>
        <mi mathvariant="normal">Σ<!-- Σ --></mi>
        <mi>k</mi>
      </msub>
      <msub>
        <mi>m</mi>
        <mrow class="MJX-TeXAtom-ORD">
          <mi>i</mi>
          <mi>k</mi>
        </mrow>
      </msub>
      <msub>
        <mi>n</mi>
        <mrow class="MJX-TeXAtom-ORD">
          <mi>k</mi>
          <mi>j</mi>
        </mrow>
      </msub>
      <mo>;</mo>
    </mtd>
  </mtr>
  <mtr>
    <mtd>
      <mtext>(transpose m)</mtext>
    </mtd>
    <mtd>
      <mtext>returns the matrix</mtext>
      <mspace width="thickmathspace"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi mathvariant="bold">n</mi>
      </mrow>
      <mo>,</mo>
    </mtd>
  </mtr>
  <mtr>
    <mtd/>
    <mtd>
      <mtext>where</mtext>
      <mspace width="thickmathspace"/>
      <msub>
        <mi>n</mi>
        <mrow class="MJX-TeXAtom-ORD">
          <mi>i</mi>
          <mi>j</mi>
        </mrow>
      </msub>
      <mo>=</mo>
      <msub>
        <mi>m</mi>
        <mrow class="MJX-TeXAtom-ORD">
          <mi>j</mi>
          <mi>i</mi>
        </mrow>
      </msub>
      <mo>.</mo>
    </mtd>
  </mtr>
</mtable>
</math>
We can define the dot product as<a class="footnote_link" id="DOCF83" href="#FOOT83"><sup>83</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dot-product v w</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate </span><span class="pun">+</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="opn">(</span><span class="pln">map </span><span class="pun">*</span><span class="pln"> v w</span><span class="clo">)))</span></pre></div>

<p>Fill in the missing expressions in the following procedures for computing the
other matrix operations.  (The procedure <code>accumulate-n</code> is defined in
<a href="#Exercise-2_002e36">Exercise 2.36</a>.)
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">matrix-</span><span class="pun">*-</span><span class="pln">vector m v</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">map ⟨</span><span class="pun">??</span><span class="pln">⟩ m</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">transpose mat</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate-n ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩ mat</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">matrix-</span><span class="pun">*-</span><span class="pln">matrix m n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">cols </span><span class="opn">(</span><span class="pln">transpose n</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">map ⟨</span><span class="pun">??</span><span class="pln">⟩ m</span><span class="clo">)))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e38"></a>Exercise 2.38:</strong> The <code>accumulate</code> procedure
is also known as <code>fold-right</code>, because it combines the first element of
the sequence with the result of combining all the elements to the right.  There
is also a <code>fold-left</code>, which is similar to <code>fold-right</code>, except that
it combines elements working in the opposite direction:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fold-left op initial sequence</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter result rest</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? rest</span><span class="clo">)</span><span class="pln">
        result
        </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="pln">op result </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> rest</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> rest</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">iter initial sequence</span><span class="clo">))</span></pre></div>

<p>What are the values of
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">fold-right </span><span class="pun">/</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">fold-left  </span><span class="pun">/</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">fold-right list nil </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">fold-left  list nil </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="clo">))</span></pre></div>

<p>Give a property that <code>op</code> should satisfy to guarantee that
<code>fold-right</code> and <code>fold-left</code> will produce the same values for any
sequence.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e39"></a>Exercise 2.39:</strong> Complete the following
definitions of <code>reverse</code> (<a href="#Exercise-2_002e18">Exercise 2.18</a>) in terms of
<code>fold-right</code> and <code>fold-left</code> from <a href="#Exercise-2_002e38">Exercise 2.38</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reverse sequence</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">fold-right 
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> nil sequence</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reverse sequence</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">fold-left 
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> nil sequence</span><span class="clo">))</span></pre></div>
</blockquote>

<a id="Nested-Mappings"></a>
<h5 class="subsubheading">Nested Mappings</h5>

<p>We can extend the sequence paradigm to include many computations that are
commonly expressed using nested loops.<a class="footnote_link" id="DOCF84" href="#FOOT84"><sup>84</sup></a> Consider this problem: Given a positive integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, find all
ordered pairs of distinct positive integers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>i</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>j</mi>
</math>, where 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mo>≤<!-- ≤ --></mo>
    <mi>j</mi>
  </mrow>
  <mo>&lt;</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>≤<!-- ≤ --></mo>
    <mi>n</mi>
  </mrow>
</math>, such that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>+</mo>
    <mi>j</mi>
  </mrow>
</math> is prime.  For example, if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is 6,
then the pairs are the following:
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="center center center center center center center center" rowspacing="4pt" columnspacing="1em" rowlines="none solid" columnlines="solid none none none none none none">
    <mtr>
      <mtd>
        <mi>i</mi>
      </mtd>
      <mtd>
        <mn>2</mn>
      </mtd>
      <mtd>
        <mn>3</mn>
      </mtd>
      <mtd>
        <mn>4</mn>
      </mtd>
      <mtd>
        <mn>4</mn>
      </mtd>
      <mtd>
        <mn>5</mn>
      </mtd>
      <mtd>
        <mn>6</mn>
      </mtd>
      <mtd>
        <mn>6</mn>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mi>j</mi>
      </mtd>
      <mtd>
        <mn>1</mn>
      </mtd>
      <mtd>
        <mn>2</mn>
      </mtd>
      <mtd>
        <mn>1</mn>
      </mtd>
      <mtd>
        <mn>3</mn>
      </mtd>
      <mtd>
        <mn>2</mn>
      </mtd>
      <mtd>
        <mn>1</mn>
      </mtd>
      <mtd>
        <mn>5</mn>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mi>i</mi>
        <mo>+</mo>
        <mi>j</mi>
      </mtd>
      <mtd>
        <mn>3</mn>
      </mtd>
      <mtd>
        <mn>5</mn>
      </mtd>
      <mtd>
        <mn>5</mn>
      </mtd>
      <mtd>
        <mn>7</mn>
      </mtd>
      <mtd>
        <mn>7</mn>
      </mtd>
      <mtd>
        <mn>7</mn>
      </mtd>
      <mtd>
        <mn>11</mn>
      </mtd>
    </mtr>
  </mtable>
</math>
A natural way to organize this computation is to generate the sequence of all
ordered pairs of positive integers less than or equal to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, filter to
select those pairs whose sum is prime, and then, for each pair <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>
that passes through the filter, produce the triple <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo>,</mo>
    <mi>i</mi>
    <mo>+</mo>
    <mi>j</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.
</p>
<p>Here is a way to generate the sequence of pairs: For each integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>≤<!-- ≤ --></mo>
    <mi>n</mi>
  </mrow>
</math>, 
enumerate the integers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>j</mi>
    <mo>&lt;</mo>
    <mi>i</mi>
  </mrow>
</math>, and for each such <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>i</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>j</mi>
</math>
generate the pair <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  In terms of sequence operations, we map along
the sequence <code>(enumerate-interval 1 n)</code>.  For each <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>i</mi>
</math> in this sequence,
we map along the sequence <code>(enumerate-interval 1 (- i 1))</code>.  For each
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>j</mi>
</math> in this latter sequence, we generate the pair <code>(list i j)</code>.  This
gives us a sequence of pairs for each <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>i</mi>
</math>.  Combining all the sequences for
all the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>i</mi>
</math> (by accumulating with <code>append</code>) produces the required
sequence of pairs:<a class="footnote_link" id="DOCF85" href="#FOOT85"><sup>85</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">accumulate 
 append
 nil
 </span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">i</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">j</span><span class="clo">)</span><span class="pln"> 
               </span><span class="opn">(</span><span class="pln">list i j</span><span class="clo">))</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">enumerate-interval </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> i </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">enumerate-interval </span><span class="lit">1</span><span class="pln"> n</span><span class="clo">)))</span></pre></div>

<p>The combination of mapping and accumulating with <code>append</code> is so common in
this sort of program that we will isolate it as a separate procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">flatmap proc seq</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate append nil </span><span class="opn">(</span><span class="pln">map proc seq</span><span class="clo">)))</span></pre></div>

<p>Now filter this sequence of pairs to find those whose sum is prime. The filter
predicate is called for each element of the sequence; its argument is a pair
and it must extract the integers from the pair.  Thus, the predicate to apply
to each element in the sequence is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">prime-sum? pair</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">prime? </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> pair</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> pair</span><span class="clo">))))</span></pre></div>

<p>Finally, generate the sequence of results by mapping over the filtered pairs
using the following procedure, which constructs a triple consisting of the two
elements of the pair along with their sum:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-pair-sum pair</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> pair</span><span class="clo">)</span><span class="pln"> 
        </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> pair</span><span class="clo">)</span><span class="pln"> 
        </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> pair</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> pair</span><span class="clo">))))</span></pre></div>

<p>Combining all these steps yields the complete procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">prime-sum-pairs n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">map make-pair-sum
       </span><span class="opn">(</span><span class="pln">filter 
        prime-sum?
        </span><span class="opn">(</span><span class="pln">flatmap
         </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">i</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">j</span><span class="clo">)</span><span class="pln"> 
                  </span><span class="opn">(</span><span class="pln">list i j</span><span class="clo">))</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">enumerate-interval 
                 </span><span class="lit">1</span><span class="pln"> 
                 </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> i </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">enumerate-interval </span><span class="lit">1</span><span class="pln"> n</span><span class="clo">)))))</span></pre></div>

<p>Nested mappings are also useful for sequences other than those that enumerate
intervals.  Suppose we wish to generate all the permutations of a set <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>S</mi>
    <mo>;</mo>
  </mrow>
</math>
that is, all the ways of ordering the items in the set.  For instance, the
permutations of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo fence="false" stretchy="false">{</mo>
    <mn>1</mn>
    <mo>,</mo>
    <mn>2</mn>
    <mo>,</mo>
    <mn>3</mn>
    <mo fence="false" stretchy="false">}</mo>
  </mrow>
</math> are <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo fence="false" stretchy="false">{</mo>
    <mn>1</mn>
    <mo>,</mo>
    <mn>2</mn>
    <mo>,</mo>
    <mn>3</mn>
    <mo fence="false" stretchy="false">}</mo>
  </mrow>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo fence="false" stretchy="false">{</mo>
    <mn>1</mn>
    <mo>,</mo>
    <mn>3</mn>
    <mo>,</mo>
    <mn>2</mn>
    <mo fence="false" stretchy="false">}</mo>
  </mrow>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo fence="false" stretchy="false">{</mo>
    <mn>2</mn>
    <mo>,</mo>
    <mn>1</mn>
    <mo>,</mo>
    <mn>3</mn>
    <mo fence="false" stretchy="false">}</mo>
  </mrow>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo fence="false" stretchy="false">{</mo>
    <mn>2</mn>
    <mo>,</mo>
    <mn>3</mn>
    <mo>,</mo>
    <mn>1</mn>
    <mo fence="false" stretchy="false">}</mo>
  </mrow>
</math>,
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo fence="false" stretchy="false">{</mo>
    <mn>3</mn>
    <mo>,</mo>
    <mn>1</mn>
    <mo>,</mo>
    <mn>2</mn>
    <mo fence="false" stretchy="false">}</mo>
  </mrow>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo fence="false" stretchy="false">{</mo>
    <mn>3</mn>
    <mo>,</mo>
    <mn>2</mn>
    <mo>,</mo>
    <mn>1</mn>
    <mo fence="false" stretchy="false">}</mo>
  </mrow>
</math>.  Here is a plan for generating the permutations of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math>: For each item <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math>, recursively generate the sequence of
permutations of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>S</mi>
    <mo>−<!-- − --></mo>
    <mi>x</mi>
  </mrow>
</math>,<a class="footnote_link" id="DOCF86" href="#FOOT86"><sup>86</sup></a> and adjoin <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> to the front of each one.
This yields, for each <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math>, the sequence of permutations of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math>
that begin with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>.  Combining these sequences for all <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> gives all the
permutations of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math>:<a class="footnote_link" id="DOCF87" href="#FOOT87"><sup>87</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">permutations s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? s</span><span class="clo">)</span><span class="pln">   </span><span class="roman"><span class="com">; empty set?</span></span><span class="pln">
      </span><span class="opn">(</span><span class="pln">list nil</span><span class="clo">)</span><span class="pln">  </span><span class="roman"><span class="com">; sequence containing empty set</span></span><span class="pln">
      </span><span class="opn">(</span><span class="pln">flatmap </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">p</span><span class="clo">)</span><span class="pln"> 
                        </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> x p</span><span class="clo">))</span><span class="pln">
                      </span><span class="opn">(</span><span class="pln">permutations 
                       </span><span class="opn">(</span><span class="pln">remove x s</span><span class="clo">))))</span><span class="pln">
               s</span><span class="clo">)))</span></pre></div>

<p>Notice how this strategy reduces the problem of generating permutations of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math> to the problem of generating the permutations of sets with fewer elements
than <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math>.  In the terminal case, we work our way down to the empty list,
which represents a set of no elements.  For this, we generate <code>(list
nil)</code>, which is a sequence with one item, namely the set with no elements.  The
<code>remove</code> procedure used in <code>permutations</code> returns all the items in a
given sequence except for a given item.  This can be expressed as a simple
filter:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">remove item sequence</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">filter </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> x item</span><span class="clo">)))</span><span class="pln">
          sequence</span><span class="clo">))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-2_002e40"></a>Exercise 2.40:</strong> Define a procedure
<code>unique-pairs</code> that, given an integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, generates the sequence of
pairs <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mo>≤<!-- ≤ --></mo>
    <mi>j</mi>
  </mrow>
  <mo>&lt;</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>≤<!-- ≤ --></mo>
    <mi>n</mi>
  </mrow>
</math>.  Use <code>unique-pairs</code>
to simplify the definition of <code>prime-sum-pairs</code> given above.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e41"></a>Exercise 2.41:</strong> Write a procedure to find all
ordered triples of distinct positive integers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>i</mi>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>j</mi>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math> less than
or equal to a given integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> that sum to a given integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>s</mi>
</math>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e42"></a>Exercise 2.42:</strong> The “eight-queens puzzle” asks
how to place eight queens on a chessboard so that no queen is in check from any
other (i.e., no two queens are in the same row, column, or diagonal).  One
possible solution is shown in <a href="#Figure-2_002e8">Figure 2.8</a>.  One way to solve the puzzle is
to work across the board, placing a queen in each column.  Once we have placed
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>k</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
</math> queens, we must place the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>k</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> queen in a position where it does
not check any of the queens already on the board.  We can formulate this
approach recursively: Assume that we have already generated the sequence of all
possible ways to place <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>k</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
</math> queens in the first <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>k</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
</math> columns of the
board.  For each of these ways, generate an extended set of positions by
placing a queen in each row of the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>k</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> column.  Now filter these, keeping
only the positions for which the queen in the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>k</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> column is safe with
respect to the other queens.  This produces the sequence of all ways to place
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math> queens in the first <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math> columns.  By continuing this process, we will
produce not only one solution, but all solutions to the puzzle.
</p>
<figure class="float">
<a id="Figure-2_002e8"></a>
<object style="width: 33.41ex; height: 33.41ex;" data="fig/chap2/Fig2.8c.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.8:</strong> A solution to the eight-queens puzzle.</p>
</figcaption>
</figure>

<p>We implement this solution as a procedure <code>queens</code>, which returns a
sequence of all solutions to the problem of placing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> queens on an
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>×<!-- × --></mo>
    <mi>n</mi>
  </mrow>
</math> chessboard.  <code>Queens</code> has an internal procedure
<code>queen-cols</code> that returns the sequence of all ways to place queens in the
first <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math> columns of the board.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">queens board-size</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">queen-cols k</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> k </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">list empty-board</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">filter
         </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">positions</span><span class="clo">)</span><span class="pln"> 
           </span><span class="opn">(</span><span class="pln">safe? k positions</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">flatmap
          </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rest-of-queens</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">new-row</span><span class="clo">)</span><span class="pln">
                   </span><span class="opn">(</span><span class="pln">adjoin-position 
                    new-row 
                    k 
                    rest-of-queens</span><span class="clo">))</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">enumerate-interval 
                  </span><span class="lit">1</span><span class="pln"> 
                  board-size</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">queen-cols </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> k </span><span class="lit">1</span><span class="clo">))))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">queen-cols board-size</span><span class="clo">))</span></pre></div>

<p>In this procedure <code>rest-of-queens</code> is a way to place <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>k</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
</math> queens in
the first <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>k</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
</math> columns, and <code>new-row</code> is a proposed row in which to
place the queen for the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>k</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> column.  Complete the program by implementing
the representation for sets of board positions, including the procedure
<code>adjoin-position</code>, which adjoins a new row-column position to a set of
positions, and <code>empty-board</code>, which represents an empty set of positions.
You must also write the procedure <code>safe?</code>, which determines for a set of
positions, whether the queen in the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>k</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> column is safe with respect to the
others.  (Note that we need only check whether the new queen is safe—the
other queens are already guaranteed safe with respect to each other.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e43"></a>Exercise 2.43:</strong> Louis Reasoner is having a
terrible time doing <a href="#Exercise-2_002e42">Exercise 2.42</a>.  His <code>queens</code> procedure seems to
work, but it runs extremely slowly.  (Louis never does manage to wait long
enough for it to solve even the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>6</mn>
    <mo>×<!-- × --></mo>
    <mn>6</mn>
  </mrow>
</math> case.)  When Louis asks Eva Lu Ator for
help, she points out that he has interchanged the order of the nested mappings
in the <code>flatmap</code>, writing it as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">flatmap
 </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">new-row</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rest-of-queens</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">adjoin-position 
           new-row k rest-of-queens</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">queen-cols </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> k </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">enumerate-interval </span><span class="lit">1</span><span class="pln"> board-size</span><span class="clo">))</span></pre></div>

<p>Explain why this interchange makes the program run slowly.  Estimate how long
it will take Louis’s program to solve the eight-queens puzzle, assuming that
the program in <a href="#Exercise-2_002e42">Exercise 2.42</a> solves the puzzle in time <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>T</mi>
</math>.
</p></blockquote>

<a id="g_t2_002e2_002e4"></a>
<a id="Example_003a-A-Picture-Language"></a>
<h4 class="subsection"><span class="secnum">2.2.4</span><span class="sectitle">Example: A Picture Language</span></h4>

<p>This section presents a simple language for drawing pictures that illustrates
the power of data abstraction and closure, and also exploits higher-order
procedures in an essential way.  The language is designed to make it easy to
experiment with patterns such as the ones in <a href="#Figure-2_002e9">Figure 2.9</a>, which are
composed of repeated elements that are shifted and scaled.<a class="footnote_link" id="DOCF88" href="#FOOT88"><sup>88</sup></a> In this language, the data
objects being combined are represented as procedures rather than as list
structure.  Just as <code>cons</code>, which satisfies the closure property, allowed
us to easily build arbitrarily complicated list structure, the operations in
this language, which also satisfy the closure property, allow us to easily
build arbitrarily complicated patterns.
</p>
<figure class="float">
<a id="Figure-2_002e9"></a>
<object style="width: 55.86ex; height: 31.34ex;" data="fig/chap2/Fig2.9.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.9:</strong> Designs generated with the picture language.</p>
</figcaption>
</figure>

<a id="The-picture-language"></a>
<h5 class="subsubheading">The picture language</h5>

<p>When we began our study of programming in <a href="1_002e1.xhtml#g_t1_002e1">1.1</a>, we emphasized the
importance of describing a language by focusing on the language’s primitives,
its means of combination, and its means of abstraction.  We’ll follow that
framework here.
</p>
<p>Part of the elegance of this picture language is that there is only one kind of
element, called a <a id="index-painter"></a>
<em>painter</em>.  A painter draws an image that is shifted
and scaled to fit within a designated parallelogram-shaped frame.  For example,
there’s a primitive painter we’ll call <code>wave</code> that makes a crude line
drawing, as shown in <a href="#Figure-2_002e10">Figure 2.10</a>.  The actual shape of the drawing
depends on the frame—all four images in figure 2.10 are produced by the
same <code>wave</code> painter, but with respect to four different frames.  Painters
can be more elaborate than this: The primitive painter called <code>rogers</code>
paints a picture of <abbr>MIT</abbr>’s founder, William Barton Rogers, as shown in
<a href="#Figure-2_002e11">Figure 2.11</a>.<a class="footnote_link" id="DOCF89" href="#FOOT89"><sup>89</sup></a> The four images in figure 2.11 are drawn with respect to the same four
frames as the <code>wave</code> images in figure 2.10.
</p>
<figure class="float">
<a id="Figure-2_002e10"></a>
<object style="width: 28.23ex; height: 30.22ex;" data="fig/chap2/Fig2.10.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.10:</strong> Images produced by the <code>wave</code> painter, with respect to four different frames.  The frames, shown with dotted lines, are not part of the images.</p>
</figcaption>
</figure>

<figure class="float">
<a id="Figure-2_002e11"></a>
<object style="width: 28.23ex; height: 31.26ex;" data="fig/chap2/Fig2.11.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.11:</strong> Images of William Barton Rogers, founder and first president of <abbr>MIT</abbr>, painted with respect to the same four frames as in <a href="#Figure-2_002e10">Figure 2.10</a> (original image from Wikimedia Commons).</p>
</figcaption>
</figure>

<p>To combine images, we use various operations that construct new painters from
given painters.  For example, the <code>beside</code> operation takes two painters
and produces a new, compound painter that draws the first painter’s image in
the left half of the frame and the second painter’s image in the right half of
the frame.  Similarly, <code>below</code> takes two painters and produces a compound
painter that draws the first painter’s image below the second painter’s image.
Some operations transform a single painter to produce a new painter.  For
example, <code>flip-vert</code> takes a painter and produces a painter that draws its
image upside-down, and <code>flip-horiz</code> produces a painter that draws the
original painter’s image left-to-right reversed.
</p>
<p><a href="#Figure-2_002e12">Figure 2.12</a> shows the drawing of a painter called
<code>wave4</code> that is built up in two stages starting from <code>wave</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> wave2 </span><span class="opn">(</span><span class="pln">beside wave </span><span class="opn">(</span><span class="pln">flip-vert wave</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> wave4 </span><span class="opn">(</span><span class="pln">below wave2 wave2</span><span class="clo">))</span></pre></div>

<figure class="float">
<a id="Figure-2_002e12"></a>
<object style="width: 47.06ex; height: 26.07ex;" data="fig/chap2/Fig2.12.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.12:</strong> Creating a complex figure, starting from the <code>wave</code> painter of <a href="#Figure-2_002e10">Figure 2.10</a>.</p>
</figcaption>
</figure>

<p>In building up a complex image in this manner we are exploiting the fact that
painters are closed under the language’s means of combination.  The
<code>beside</code> or <code>below</code> of two painters is itself a painter; therefore,
we can use it as an element in making more complex painters.  As with building
up list structure using <code>cons</code>, the closure of our data under the means of
combination is crucial to the ability to create complex structures while using
only a few operations.
</p>
<p>Once we can combine painters, we would like to be able to abstract typical
patterns of combining painters.  We will implement the painter operations as
Scheme procedures.  This means that we don’t need a special abstraction
mechanism in the picture language: Since the means of combination are ordinary
Scheme procedures, we automatically have the capability to do anything with
painter operations that we can do with procedures.  For example, we can
abstract the pattern in <code>wave4</code> as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">flipped-pairs painter</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">painter2 
         </span><span class="opn">(</span><span class="pln">beside painter 
                 </span><span class="opn">(</span><span class="pln">flip-vert painter</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">below painter2 painter2</span><span class="clo">)))</span></pre></div>

<p>and define <code>wave4</code> as an instance of this pattern:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> wave4 </span><span class="opn">(</span><span class="pln">flipped-pairs wave</span><span class="clo">))</span></pre></div>

<p>We can also define recursive operations.  Here’s one that makes painters split
and branch towards the right as shown in <a href="#Figure-2_002e13">Figure 2.13</a>
and <a href="#Figure-2_002e14">Figure 2.14</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">right-split painter n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      painter
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">smaller </span><span class="opn">(</span><span class="pln">right-split painter 
                                  </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">beside painter 
                </span><span class="opn">(</span><span class="pln">below smaller smaller</span><span class="clo">)))))</span></pre></div>

<figure class="float">
<a id="Figure-2_002e13"></a>
<object style="width: 52.15ex; height: 68.90ex;" data="fig/chap2/Fig2.13a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.13:</strong> Recursive plans for <code>right-split</code> and <code>corner-split</code>.</p>
</figcaption>
</figure>

<p>We can produce balanced patterns by branching upwards as well as towards the
right (see <a href="#Exercise-2_002e44">Exercise 2.44</a>, <a href="#Figure-2_002e13">Figure 2.13</a> and <a href="#Figure-2_002e14">Figure 2.14</a>):
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">corner-split painter n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      painter
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">up </span><span class="opn">(</span><span class="pln">up-split painter </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">right </span><span class="opn">(</span><span class="pln">right-split painter 
                                </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">top-left </span><span class="opn">(</span><span class="pln">beside up up</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">bottom-right </span><span class="opn">(</span><span class="pln">below right 
                                   right</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">corner </span><span class="opn">(</span><span class="pln">corner-split painter 
                                    </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">beside </span><span class="opn">(</span><span class="pln">below painter top-left</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">below bottom-right 
                         corner</span><span class="clo">))))))</span></pre></div>

<figure class="float">
<a id="Figure-2_002e14"></a>
<object style="width: 52.93ex; height: 62.25ex;" data="fig/chap2/Fig2.14b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.14:</strong> The recursive operations <code>right-split</code> and <code>corner-split</code> applied to the painters <code>wave</code> and <code>rogers</code>.  Combining four <code>corner-split</code> figures produces symmetric <code>square-limit</code> designs as shown in <a href="#Figure-2_002e9">Figure 2.9</a>.</p>
</figcaption>
</figure>

<p>By placing four copies of a <code>corner-split</code> appropriately, we obtain a
pattern called <code>square-limit</code>, whose application to <code>wave</code> and
<code>rogers</code> is shown in <a href="#Figure-2_002e9">Figure 2.9</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square-limit painter n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">quarter </span><span class="opn">(</span><span class="pln">corner-split painter n</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">half </span><span class="opn">(</span><span class="pln">beside </span><span class="opn">(</span><span class="pln">flip-horiz quarter</span><span class="clo">)</span><span class="pln"> 
                        quarter</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">below </span><span class="opn">(</span><span class="pln">flip-vert half</span><span class="clo">)</span><span class="pln"> half</span><span class="clo">))))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-2_002e44"></a>Exercise 2.44:</strong> Define the procedure
<code>up-split</code> used by <code>corner-split</code>.  It is similar to
<code>right-split</code>, except that it switches the roles of <code>below</code> and
<code>beside</code>.
</p></blockquote>

<a id="Higher_002dorder-operations"></a>
<h5 class="subsubheading">Higher-order operations</h5>

<p>In addition to abstracting patterns of combining painters, we can work at a
higher level, abstracting patterns of combining painter operations.  That is,
we can view the painter operations as elements to manipulate and can write
means of combination for these elements—procedures that take painter
operations as arguments and create new painter operations.
</p>
<p>For example, <code>flipped-pairs</code> and <code>square-limit</code> each arrange four
copies of a painter’s image in a square pattern; they differ only in how they
orient the copies.  One way to abstract this pattern of painter combination is
with the following procedure, which takes four one-argument painter operations
and produces a painter operation that transforms a given painter with those
four operations and arranges the results in a square.  <code>Tl</code>, <code>tr</code>,
<code>bl</code>, and <code>br</code> are the transformations to apply to the top left copy,
the top right copy, the bottom left copy, and the bottom right copy,
respectively.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square-of-four tl tr bl br</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">painter</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">top </span><span class="opn">(</span><span class="pln">beside </span><span class="opn">(</span><span class="pln">tl painter</span><span class="clo">)</span><span class="pln"> 
                       </span><span class="opn">(</span><span class="pln">tr painter</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">bottom </span><span class="opn">(</span><span class="pln">beside </span><span class="opn">(</span><span class="pln">bl painter</span><span class="clo">)</span><span class="pln"> 
                          </span><span class="opn">(</span><span class="pln">br painter</span><span class="clo">))))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">below bottom top</span><span class="clo">))))</span></pre></div>

<p>Then <code>flipped-pairs</code> can be defined in terms of <code>square-of-four</code> as
follows:<a class="footnote_link" id="DOCF90" href="#FOOT90"><sup>90</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">flipped-pairs painter</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">combine4 
         </span><span class="opn">(</span><span class="pln">square-of-four identity 
                         flip-vert
                         identity 
                         flip-vert</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">combine4 painter</span><span class="clo">)))</span></pre></div>

<p>and <code>square-limit</code> can be expressed as<a class="footnote_link" id="DOCF91" href="#FOOT91"><sup>91</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square-limit painter n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">combine4 
         </span><span class="opn">(</span><span class="pln">square-of-four flip-horiz 
                         identity
                         rotate180 
                         flip-vert</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">combine4 </span><span class="opn">(</span><span class="pln">corner-split painter n</span><span class="clo">))))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-2_002e45"></a>Exercise 2.45:</strong> <code>Right-split</code> and
<code>up-split</code> can be expressed as instances of a general splitting operation.
Define a procedure <code>split</code> with the property that evaluating
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> right-split </span><span class="opn">(</span><span class="pln">split beside below</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> up-split </span><span class="opn">(</span><span class="pln">split below beside</span><span class="clo">))</span></pre></div>

<p>produces procedures <code>right-split</code> and <code>up-split</code> with the same
behaviors as the ones already defined.
</p></blockquote>

<a id="Frames"></a>
<h5 class="subsubheading">Frames</h5>

<p>Before we can show how to implement painters and their means of combination, we
must first consider frames.  A frame can be described by three vectors—an
origin vector and two edge vectors.  The origin vector specifies the offset of
the frame’s origin from some absolute origin in the plane, and the edge vectors
specify the offsets of the frame’s corners from its origin.  If the edges are
perpendicular, the frame will be rectangular.  Otherwise the frame will be a
more general parallelogram.
</p>
<p><a href="#Figure-2_002e15">Figure 2.15</a> shows a frame and its associated vectors.
In accordance with data abstraction, we need not be specific yet about how
frames are represented, other than to say that there is a constructor
<code>make-frame</code>, which takes three vectors and produces a frame, and three
corresponding selectors <code>origin-frame</code>, <code>edge1-frame</code>, and
<code>edge2-frame</code> (see <a href="#Exercise-2_002e47">Exercise 2.47</a>).
</p>
<figure class="float">
<a id="Figure-2_002e15"></a>
<object style="width: 34.02ex; height: 32.03ex;" data="fig/chap2/Fig2.15a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.15:</strong> A frame is described by three vectors — an origin and two edges.</p>
</figcaption>
</figure>

<p>We will use coordinates in the unit square <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mn>0</mn>
    <mo>≤<!-- ≤ --></mo>
    <mi>x</mi>
    <mo>,</mo>
    <mi>y</mi>
    <mo>≤<!-- ≤ --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math> to specify
images.  With each frame, we associate a <a id="index-frame-coordinate-map"></a>
<em>frame coordinate map</em>, which
will be used to shift and scale images to fit the frame.  The map transforms
the unit square into the frame by mapping the vector <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mi mathvariant="bold">v</mi>
    </mrow>
    <mo>=</mo>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo>,</mo>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> to
the vector sum
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Origin(Frame)</mtext>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo>⋅<!-- ⋅ --></mo>
    <msub>
      <mtext>Edge</mtext>
      <mn>1</mn>
    </msub>
    <mtext>(Frame)</mtext>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo>⋅<!-- ⋅ --></mo>
    <msub>
      <mtext>Edge</mtext>
      <mn>2</mn>
    </msub>
    <mtext>(Frame)</mtext>
    <mo>.</mo>
  </mrow>
</math>
For example, (0, 0) is mapped to the origin of the frame, (1, 1) to the vertex
diagonally opposite the origin, and (0.5, 0.5) to the center of the frame.  We
can create a frame’s coordinate map with the following
procedure:<a class="footnote_link" id="DOCF92" href="#FOOT92"><sup>92</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">frame-coord-map frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">v</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">add-vect
     </span><span class="opn">(</span><span class="pln">origin-frame frame</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">add-vect 
      </span><span class="opn">(</span><span class="pln">scale-vect </span><span class="opn">(</span><span class="pln">xcor-vect v</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">edge1-frame frame</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">scale-vect </span><span class="opn">(</span><span class="pln">ycor-vect v</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">edge2-frame frame</span><span class="clo">))))))</span></pre></div>

<p>Observe that applying <code>frame-coord-map</code> to a frame returns a procedure
that, given a vector, returns a vector.  If the argument vector is in the unit
square, the result vector will be in the frame.  For example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="pln">frame-coord-map a-frame</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">0</span><span class="pln"> </span><span class="lit">0</span><span class="clo">))</span></pre></div>

<p>returns the same vector as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">origin-frame a-frame</span><span class="clo">)</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-2_002e46"></a>Exercise 2.46:</strong> A two-dimensional vector <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi mathvariant="bold">v</mi>
</math>
running from the origin to a point can be represented as a pair consisting of
an <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>-coordinate and a <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math>-coordinate.  Implement a data abstraction for
vectors by giving a constructor <code>make-vect</code> and corresponding selectors
<code>xcor-vect</code> and <code>ycor-vect</code>.  In terms of your selectors and
constructor, implement procedures <code>add-vect</code>, <code>sub-vect</code>, and
<code>scale-vect</code> that perform the operations vector addition, vector
subtraction, and multiplying a vector by a scalar:
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="right center left" rowspacing="3pt" columnspacing="thickmathspace">
    <mtr>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>x</mi>
          <mn>1</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>y</mi>
          <mn>1</mn>
        </msub>
        <mo stretchy="false">)</mo>
        <mo>+</mo>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>x</mi>
          <mn>2</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>y</mi>
          <mn>2</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>x</mi>
          <mn>1</mn>
        </msub>
        <mo>+</mo>
        <msub>
          <mi>x</mi>
          <mn>2</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>y</mi>
          <mn>1</mn>
        </msub>
        <mo>+</mo>
        <msub>
          <mi>y</mi>
          <mn>2</mn>
        </msub>
        <mo stretchy="false">)</mo>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>x</mi>
          <mn>1</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>y</mi>
          <mn>1</mn>
        </msub>
        <mo stretchy="false">)</mo>
        <mo>−<!-- − --></mo>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>x</mi>
          <mn>2</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>y</mi>
          <mn>2</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>x</mi>
          <mn>1</mn>
        </msub>
        <mo>−<!-- − --></mo>
        <msub>
          <mi>x</mi>
          <mn>2</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>y</mi>
          <mn>1</mn>
        </msub>
        <mo>−<!-- − --></mo>
        <msub>
          <mi>y</mi>
          <mn>2</mn>
        </msub>
        <mo stretchy="false">)</mo>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mi>s</mi>
        <mo>⋅<!-- ⋅ --></mo>
        <mo stretchy="false">(</mo>
        <mi>x</mi>
        <mo>,</mo>
        <mi>y</mi>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <mi>s</mi>
        <mi>x</mi>
        <mo>,</mo>
        <mi>s</mi>
        <mi>y</mi>
        <mo stretchy="false">)</mo>
        <mo>.</mo>
      </mtd>
    </mtr>
  </mtable>
</math>
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e47"></a>Exercise 2.47:</strong> Here are two possible
constructors for frames:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-frame origin edge1 edge2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">list origin edge1 edge2</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-frame origin edge1 edge2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> origin </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> edge1 edge2</span><span class="clo">)))</span></pre></div>

<p>For each constructor supply the appropriate selectors to produce an
implementation for frames.
</p></blockquote>

<a id="Painters"></a>
<h5 class="subsubheading">Painters</h5>

<p>A painter is represented as a procedure that, given a frame as argument, draws
a particular image shifted and scaled to fit the frame.  That is to say, if
<code>p</code> is a painter and <code>f</code> is a frame, then we produce <code>p</code>’s image
in <code>f</code> by calling <code>p</code> with <code>f</code> as argument.
</p>
<p>The details of how primitive painters are implemented depend on the particular
characteristics of the graphics system and the type of image to be drawn.  For
instance, suppose we have a procedure <code>draw-line</code> that draws a line on the
screen between two specified points.  Then we can create painters for line
drawings, such as the <code>wave</code> painter in <a href="#Figure-2_002e10">Figure 2.10</a>, from lists of
line segments as follows:<a class="footnote_link" id="DOCF93" href="#FOOT93"><sup>93</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">segments-</span><span class="pun">&gt;</span><span class="pln">painter segment-list</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">frame</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">for-each
     </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">segment</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">draw-line
        </span><span class="opn">((</span><span class="pln">frame-coord-map frame</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">start-segment segment</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">frame-coord-map frame</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">end-segment segment</span><span class="clo">))))</span><span class="pln">
     segment-list</span><span class="clo">)))</span></pre></div>

<p>The segments are given using coordinates with respect to the unit square.  For
each segment in the list, the painter transforms the segment endpoints with the
frame coordinate map and draws a line between the transformed points.
</p>
<p>Representing painters as procedures erects a powerful abstraction barrier in
the picture language.  We can create and intermix all sorts of primitive
painters, based on a variety of graphics capabilities. The details of their
implementation do not matter.  Any procedure can serve as a painter, provided
that it takes a frame as argument and draws something scaled to fit the
frame.<a class="footnote_link" id="DOCF94" href="#FOOT94"><sup>94</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e48"></a>Exercise 2.48:</strong> A directed line segment in the
plane can be represented as a pair of vectors—the vector running from the
origin to the start-point of the segment, and the vector running from the
origin to the end-point of the segment.  Use your vector representation from
<a href="#Exercise-2_002e46">Exercise 2.46</a> to define a representation for segments with a constructor
<code>make-segment</code> and selectors <code>start-segment</code> and <code>end-segment</code>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e49"></a>Exercise 2.49:</strong> Use <code>segments-&gt;painter</code>
to define the following primitive painters:
</p>
<ol>
<li> The painter that draws the outline of the designated frame.

</li><li> The painter that draws an “X” by connecting opposite corners of the frame.

</li><li> The painter that draws a diamond shape by connecting the midpoints of the sides
of the frame.

</li><li> The <code>wave</code> painter.

</li></ol>
</blockquote>

<a id="Transforming-and-combining-painters"></a>
<h5 class="subsubheading">Transforming and combining painters</h5>

<p>An operation on painters (such as <code>flip-vert</code> or <code>beside</code>) works by
creating a painter that invokes the original painters with respect to frames
derived from the argument frame.  Thus, for example, <code>flip-vert</code> doesn’t
have to know how a painter works in order to flip it—it just has to know how
to turn a frame upside down: The flipped painter just uses the original
painter, but in the inverted frame.
</p>
<p>Painter operations are based on the procedure <code>transform-painter</code>, which
takes as arguments a painter and information on how to transform a frame and
produces a new painter.  The transformed painter, when called on a frame,
transforms the frame and calls the original painter on the transformed frame.
The arguments to <code>transform-painter</code> are points (represented as vectors)
that specify the corners of the new frame: When mapped into the frame, the
first point specifies the new frame’s origin and the other two specify the ends
of its edge vectors.  Thus, arguments within the unit square specify a frame
contained within the original frame.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">transform-painter 
         painter origin corner1 corner2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">frame</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">m </span><span class="opn">(</span><span class="pln">frame-coord-map frame</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">new-origin </span><span class="opn">(</span><span class="pln">m origin</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">painter </span><span class="opn">(</span><span class="pln">make-frame new-origin
                  </span><span class="opn">(</span><span class="pln">sub-vect </span><span class="opn">(</span><span class="pln">m corner1</span><span class="clo">)</span><span class="pln"> 
                            new-origin</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">sub-vect </span><span class="opn">(</span><span class="pln">m corner2</span><span class="clo">)</span><span class="pln">
                            new-origin</span><span class="clo">)))))))</span></pre></div>

<p>Here’s how to flip painter images vertically:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">flip-vert painter</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">transform-painter 
   painter
   </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">0.0</span><span class="pln"> </span><span class="lit">1.0</span><span class="clo">)</span><span class="pln">   </span><span class="roman"><span class="com">; new </span><code><span class="com">origin</span></code></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">1.0</span><span class="pln"> </span><span class="lit">1.0</span><span class="clo">)</span><span class="pln">   </span><span class="roman"><span class="com">; new end of </span><code><span class="com">edge1</span></code></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">0.0</span><span class="pln"> </span><span class="lit">0.0</span><span class="clo">)))</span><span class="pln"> </span><span class="roman"><span class="com">; new end of </span><code><span class="com">edge2</span></code></span>
</pre></div>

<p>Using <code>transform-painter</code>, we can easily define new transformations.
For example, we can define a painter that shrinks its image to the
upper-right quarter of the frame it is given:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">shrink-to-upper-right painter</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">transform-painter painter
                     </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">0.5</span><span class="pln"> </span><span class="lit">0.5</span><span class="clo">)</span><span class="pln">
                     </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">1.0</span><span class="pln"> </span><span class="lit">0.5</span><span class="clo">)</span><span class="pln">
                     </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">0.5</span><span class="pln"> </span><span class="lit">1.0</span><span class="clo">)))</span></pre></div>

<p>Other transformations rotate images counterclockwise by 90
degrees<a class="footnote_link" id="DOCF95" href="#FOOT95"><sup>95</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rotate90 painter</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">transform-painter painter
                     </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">1.0</span><span class="pln"> </span><span class="lit">0.0</span><span class="clo">)</span><span class="pln">
                     </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">1.0</span><span class="pln"> </span><span class="lit">1.0</span><span class="clo">)</span><span class="pln">
                     </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">0.0</span><span class="pln"> </span><span class="lit">0.0</span><span class="clo">)))</span></pre></div>

<p>or squash images towards the center of the frame:<a class="footnote_link" id="DOCF96" href="#FOOT96"><sup>96</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">squash-inwards painter</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">transform-painter painter
                     </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">0.0</span><span class="pln"> </span><span class="lit">0.0</span><span class="clo">)</span><span class="pln">
                     </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">0.65</span><span class="pln"> </span><span class="lit">0.35</span><span class="clo">)</span><span class="pln">
                     </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">0.35</span><span class="pln"> </span><span class="lit">0.65</span><span class="clo">)))</span></pre></div>

<p>Frame transformation is also the key to defining means of combining two or more
painters.  The <code>beside</code> procedure, for example, takes two painters,
transforms them to paint in the left and right halves of an argument frame
respectively, and produces a new, compound painter.  When the compound painter
is given a frame, it calls the first transformed painter to paint in the left
half of the frame and calls the second transformed painter to paint in the
right half of the frame:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">beside painter1 painter2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">split-point </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">0.5</span><span class="pln"> </span><span class="lit">0.0</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">paint-left  </span><span class="opn">(</span><span class="pln">transform-painter 
                        painter1
                        </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">0.0</span><span class="pln"> </span><span class="lit">0.0</span><span class="clo">)</span><span class="pln">
                        split-point
                        </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">0.0</span><span class="pln"> </span><span class="lit">1.0</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">paint-right </span><span class="opn">(</span><span class="pln">transform-painter
                        painter2
                        split-point
                        </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">1.0</span><span class="pln"> </span><span class="lit">0.0</span><span class="clo">)</span><span class="pln">
                        </span><span class="opn">(</span><span class="pln">make-vect </span><span class="lit">0.5</span><span class="pln"> </span><span class="lit">1.0</span><span class="clo">))))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">frame</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">paint-left frame</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">paint-right frame</span><span class="clo">)))))</span></pre></div>

<p>Observe how the painter data abstraction, and in particular the representation
of painters as procedures, makes <code>beside</code> easy to implement.  The
<code>beside</code> procedure need not know anything about the details of the
component painters other than that each painter will draw something in its
designated frame.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e50"></a>Exercise 2.50:</strong> Define the transformation
<code>flip-horiz</code>, which flips painters horizontally, and transformations that
rotate painters counterclockwise by 180 degrees and 270 degrees.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e51"></a>Exercise 2.51:</strong> Define the <code>below</code> operation
for painters.  <code>Below</code> takes two painters as arguments.  The resulting
painter, given a frame, draws with the first painter in the bottom of the frame
and with the second painter in the top.  Define <code>below</code> in two different
ways—first by writing a procedure that is analogous to the <code>beside</code>
procedure given above, and again in terms of <code>beside</code> and suitable
rotation operations (from <a href="#Exercise-2_002e50">Exercise 2.50</a>).
</p></blockquote>

<a id="Levels-of-language-for-robust-design"></a>
<h5 class="subsubheading">Levels of language for robust design</h5>

<p>The picture language exercises some of the critical ideas we’ve introduced
about abstraction with procedures and data.  The fundamental data abstractions,
painters, are implemented using procedural representations, which enables the
language to handle different basic drawing capabilities in a uniform way.  The
means of combination satisfy the closure property, which permits us to easily
build up complex designs.  Finally, all the tools for abstracting procedures
are available to us for abstracting means of combination for painters.
</p>
<p>We have also obtained a glimpse of another crucial idea about languages and
program design.  This is the approach of <a id="index-stratified-design"></a>
<em>stratified design</em>, the
notion that a complex system should be structured as a sequence of levels that
are described using a sequence of languages.  Each level is constructed by
combining parts that are regarded as primitive at that level, and the parts
constructed at each level are used as primitives at the next level.  The
language used at each level of a stratified design has primitives, means of
combination, and means of abstraction appropriate to that level of detail.
</p>
<p>Stratified design pervades the engineering of complex systems.  For example, in
computer engineering, resistors and transistors are combined (and described
using a language of analog circuits) to produce parts such as and-gates and
or-gates, which form the primitives of a language for digital-circuit
design.<a class="footnote_link" id="DOCF97" href="#FOOT97"><sup>97</sup></a> These parts
are combined to build processors, bus structures, and memory systems, which are
in turn combined to form computers, using languages appropriate to computer
architecture.  Computers are combined to form distributed systems, using
languages appropriate for describing network interconnections, and so on.
</p>
<p>As a tiny example of stratification, our picture language uses primitive
elements (primitive painters) that are created using a language that specifies
points and lines to provide the lists of line segments for
<code>segments-&gt;painter</code>, or the shading details for a painter like
<code>rogers</code>.  The bulk of our description of the picture language focused on
combining these primitives, using geometric combiners such as <code>beside</code> and
<code>below</code>.  We also worked at a higher level, regarding <code>beside</code> and
<code>below</code> as primitives to be manipulated in a language whose operations,
such as <code>square-of-four</code>, capture common patterns of combining geometric
combiners.
</p>
<p>Stratified design helps make programs <a id="index-robust"></a>
<em>robust</em>, that is, it makes it
likely that small changes in a specification will require correspondingly small
changes in the program.  For instance, suppose we wanted to change the image
based on <code>wave</code> shown in <a href="#Figure-2_002e9">Figure 2.9</a>.  We could work at the lowest
level to change the detailed appearance of the <code>wave</code> element; we could
work at the middle level to change the way <code>corner-split</code> replicates the
<code>wave</code>; we could work at the highest level to change how
<code>square-limit</code> arranges the four copies of the corner.  In general, each
level of a stratified design provides a different vocabulary for expressing the
characteristics of the system, and a different kind of ability to change it.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e52"></a>Exercise 2.52:</strong> Make changes to the square limit
of <code>wave</code> shown in <a href="#Figure-2_002e9">Figure 2.9</a> by working at each of the levels
described above.  In particular:
</p>
<ol>
<li> Add some segments to the primitive <code>wave</code> painter of <a href="#Exercise-2_002e49">Exercise 2.49</a>
(to add a smile, for example).

</li><li> Change the pattern constructed by <code>corner-split</code> (for example, by using
only one copy of the <code>up-split</code> and <code>right-split</code> images instead of
two).

</li><li> Modify the version of <code>square-limit</code> that uses <code>square-of-four</code> so as
to assemble the corners in a different pattern.  (For example, you might make
the big Mr. Rogers look outward from each corner of the square.)

</li></ol>
</blockquote>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT72"><p><a class="footnote_backlink" href="#DOCF72"><sup>72</sup></a>
The use of the word “closure” here comes from abstract
algebra, where a set of elements is said to be closed under an operation if
applying the operation to elements in the set produces an element that is again
an element of the set.  The Lisp community also (unfortunately) uses the word
“closure” to describe a totally unrelated concept: A closure is an
implementation technique for representing procedures with free variables.  We
do not use the word “closure” in this second sense in this book.  </p>
</div>
<div id="FOOT73"><p><a class="footnote_backlink" href="#DOCF73"><sup>73</sup></a>
The notion that a means of combination should satisfy
closure is a straightforward idea.  Unfortunately, the data combiners provided
in many popular programming languages do not satisfy closure, or make closure
cumbersome to exploit.  In Fortran or Basic, one typically combines data
elements by assembling them into arrays—but one cannot form arrays whose
elements are themselves arrays.  Pascal and C admit structures whose elements
are structures.  However, this requires that the programmer manipulate pointers
explicitly, and adhere to the restriction that each field of a structure can
contain only elements of a prespecified form.  Unlike Lisp with its pairs,
these languages have no built-in general-purpose glue that makes it easy to
manipulate compound data in a uniform way.  This limitation lies behind Alan
Perlis’s comment in his foreword to this book: “In Pascal the plethora of
declarable data structures induces a specialization within functions that
inhibits and penalizes casual cooperation.  It is better to have 100 functions
operate on one data structure than to have 10 functions operate on 10 data
structures.”</p>
</div>
<div id="FOOT74"><p><a class="footnote_backlink" href="#DOCF74"><sup>74</sup></a>
In this book, we use <a id="index-list-1"></a>
<em>list</em> to mean a
chain of pairs terminated by the end-of-list marker.  In contrast, the term
<a id="index-list-structure"></a>
<em>list structure</em> refers to any data structure made out of pairs, not
just to lists.</p>
</div>
<div id="FOOT75"><p><a class="footnote_backlink" href="#DOCF75"><sup>75</sup></a>
Since nested
applications of <code>car</code> and <code>cdr</code> are cumbersome to write, Lisp
dialects provide abbreviations for them—for instance,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> ⟨</span><var><span class="pln">arg</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> ⟨</span><var><span class="pln">arg</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>The names of all such procedures start with <code>c</code> and end with <code>r</code>.
Each <code>a</code> between them stands for a <code>car</code> operation and each <code>d</code>
for a <code>cdr</code> operation, to be applied in the same order in which they
appear in the name.  The names <code>car</code> and <code>cdr</code> persist because simple
combinations like <code>cadr</code> are pronounceable.</p>
</div>
<div id="FOOT76"><p><a class="footnote_backlink" href="#DOCF76"><sup>76</sup></a>
It’s remarkable how much energy in the standardization of
Lisp dialects has been dissipated in arguments that are literally over nothing:
Should <code>nil</code> be an ordinary name?  Should the value of <code>nil</code> be a
symbol?  Should it be a list?  Should it be a pair?  In Scheme, <code>nil</code> is
an ordinary name, which we use in this section as a variable whose value is the
end-of-list marker (just as <code>true</code> is an ordinary variable that has a true
value).  Other dialects of Lisp, including Common Lisp, treat <code>nil</code> as a
special symbol.  The authors of this book, who have endured too many language
standardization brawls, would like to avoid the entire issue.  Once we have
introduced quotation in <a href="2_002e3.xhtml#g_t2_002e3">2.3</a>, we will denote the empty list as
<code>'()</code> and dispense with the variable <code>nil</code> entirely.</p>
</div>
<div id="FOOT77"><p><a class="footnote_backlink" href="#DOCF77"><sup>77</sup></a>
To define <code>f</code> and <code>g</code> using <code>lambda</code> we would
write
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> f </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y </span><span class="pun">.</span><span class="pln"> z</span><span class="clo">)</span><span class="pln"> ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> g </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> w ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>
</div>
<div id="FOOT78"><p><a class="footnote_backlink" href="#DOCF78"><sup>78</sup></a>
<a id="Footnote-78"></a>Scheme standardly provides a <code>map</code> procedure that
is more general than the one described here.  This more general <code>map</code>
takes a procedure of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> arguments, together with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> lists, and applies
the procedure to all the first elements of the lists, all the second elements
of the lists, and so on, returning a list of the results.  For example:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">map </span><span class="pun">+</span><span class="pln"> 
     </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="clo">)</span><span class="pln"> 
     </span><span class="opn">(</span><span class="pln">list </span><span class="lit">40</span><span class="pln"> </span><span class="lit">50</span><span class="pln"> </span><span class="lit">60</span><span class="clo">)</span><span class="pln"> 
     </span><span class="opn">(</span><span class="pln">list </span><span class="lit">700</span><span class="pln"> </span><span class="lit">800</span><span class="pln"> </span><span class="lit">900</span><span class="clo">))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">741</span><span class="pln"> </span><span class="lit">852</span><span class="pln"> </span><span class="lit">963</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> y</span><span class="clo">)))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">list </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">list </span><span class="lit">4</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="lit">6</span><span class="clo">))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">9</span><span class="pln"> </span><span class="lit">12</span><span class="pln"> </span><span class="lit">15</span><span class="clo">)</span></i>
</pre></div>
</div>
<div id="FOOT79"><p><a class="footnote_backlink" href="#DOCF79"><sup>79</sup></a>
The order of the first two clauses in the
<code>cond</code> matters, since the empty list satisfies <code>null?</code> and also is
not a pair.</p>
</div>
<div id="FOOT80"><p><a class="footnote_backlink" href="#DOCF80"><sup>80</sup></a>
This is, in fact,
precisely the <code>fringe</code> procedure from <a href="#Exercise-2_002e28">Exercise 2.28</a>.  Here we’ve
renamed it to emphasize that it is part of a family of general
sequence-manipulation procedures.</p>
</div>
<div id="FOOT81"><p><a class="footnote_backlink" href="#DOCF81"><sup>81</sup></a>
Richard <a href="References.xhtml#Waters-_00281979_0029">Waters (1979)</a> developed a
program that automatically analyzes traditional Fortran programs, viewing them
in terms of maps, filters, and accumulations.  He found that fully 90 percent
of the code in the Fortran Scientific Subroutine Package fits neatly into this
paradigm.  One of the reasons for the success of Lisp as a programming language
is that lists provide a standard medium for expressing ordered collections so
that they can be manipulated using higher-order operations.  The programming
language APL owes much of its power and appeal to a similar choice. In APL all
data are represented as arrays, and there is a universal and convenient set of
generic operators for all sorts of array operations.</p>
</div>
<div id="FOOT82"><p><a class="footnote_backlink" href="#DOCF82"><sup>82</sup></a>
According to <a href="References.xhtml#Knuth-1981">Knuth 1981</a>, this rule was formulated by
W. G. Horner early in the nineteenth century, but the method was actually used
by Newton over a hundred years earlier.  Horner’s rule evaluates the polynomial
using fewer additions and multiplications than does the straightforward method
of first computing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mi>n</mi>
    </msub>
    <msup>
      <mi>x</mi>
      <mi>n</mi>
    </msup>
  </mrow>
</math>, then adding
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>n</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <msup>
      <mi>x</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>n</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msup>
  </mrow>
</math>, and so on.  In fact, it is possible to prove
that any algorithm for evaluating arbitrary polynomials must use at least as
many additions and multiplications as does Horner’s rule, and thus Horner’s
rule is an optimal algorithm for polynomial evaluation.  This was proved (for
the number of additions) by A. M. Ostrowski in a 1954 paper that essentially
founded the modern study of optimal algorithms.  The analogous statement for
multiplications was proved by V. Y. Pan in 1966.  The book by <a href="References.xhtml#Borodin-and-Munro-_00281975_0029">Borodin and Munro (1975)</a> 
provides an overview of these and other results about optimal
algorithms.</p>
</div>
<div id="FOOT83"><p><a class="footnote_backlink" href="#DOCF83"><sup>83</sup></a>
This definition uses the extended
version of <code>map</code> described in <a href="#Footnote-78">Footnote 78</a>.</p>
</div>
<div id="FOOT84"><p><a class="footnote_backlink" href="#DOCF84"><sup>84</sup></a>
This approach to nested
mappings was shown to us by David Turner, whose languages KRC and Miranda
provide elegant formalisms for dealing with these constructs.  The examples in
this section (see also <a href="#Exercise-2_002e42">Exercise 2.42</a>) are adapted from <a href="References.xhtml#Turner-1981">Turner 1981</a>.  In
<a href="3_002e5.xhtml#g_t3_002e5_002e3">3.5.3</a>, we’ll see how this approach generalizes to infinite
sequences.</p>
</div>
<div id="FOOT85"><p><a class="footnote_backlink" href="#DOCF85"><sup>85</sup></a>
We’re representing a pair here as a list of two
elements rather than as a Lisp pair.  Thus, the “pair” <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> is
represented as <code>(list i j)</code>, not <code>(cons i j)</code>.</p>
</div>
<div id="FOOT86"><p><a class="footnote_backlink" href="#DOCF86"><sup>86</sup></a>
The set <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>S</mi>
    <mo>−<!-- − --></mo>
    <mi>x</mi>
  </mrow>
</math> is the set of all
elements of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math>, excluding <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>.</p>
</div>
<div id="FOOT87"><p><a class="footnote_backlink" href="#DOCF87"><sup>87</sup></a>
Semicolons in Scheme code are used to introduce
<a id="index-comments"></a>
<em>comments</em>.  Everything from the semicolon to the end of the line is
ignored by the interpreter.  In this book we don’t use many comments; we try to
make our programs self-documenting by using descriptive names.</p>
</div>
<div id="FOOT88"><p><a class="footnote_backlink" href="#DOCF88"><sup>88</sup></a>
The picture
language is based on the language Peter Henderson created to construct images
like M.C. Escher’s “Square Limit” woodcut (see <a href="References.xhtml#Henderson-1982">Henderson 1982</a>).  The woodcut
incorporates a repeated scaled pattern, similar to the arrangements drawn using
the <code>square-limit</code> procedure in this section.</p>
</div>
<div id="FOOT89"><p><a class="footnote_backlink" href="#DOCF89"><sup>89</sup></a>
William Barton Rogers (1804-1882) was the founder
and first president of <abbr>MIT</abbr>.  A geologist and talented teacher, he
taught at William and Mary College and at the University of Virginia.  In 1859
he moved to Boston, where he had more time for research, worked on a plan for
establishing a “polytechnic institute,” and served as Massachusetts’s first
State Inspector of Gas Meters.
</p>
<p>When <abbr>MIT</abbr> was established in 1861, Rogers was elected its first
president.  Rogers espoused an ideal of “useful learning” that was different
from the university education of the time, with its overemphasis on the
classics, which, as he wrote, “stand in the way of the broader, higher and
more practical instruction and discipline of the natural and social sciences.”
This education was likewise to be different from narrow trade-school education.
In Rogers’s words:
</p>
<blockquote>
<p>The world-enforced distinction between the practical and the scientific worker
is utterly futile, and the whole experience of modern times has demonstrated
its utter worthlessness.
</p></blockquote>

<p>Rogers served as president of <abbr>MIT</abbr> until 1870, when he resigned due to
ill health.  In 1878 the second president of <abbr>MIT</abbr>, John Runkle,
resigned under the pressure of a financial crisis brought on by the Panic of
1873 and strain of fighting off attempts by Harvard to take over <abbr>MIT</abbr>.
Rogers returned to hold the office of president until 1881.
</p>
<p>Rogers collapsed and died while addressing <abbr>MIT</abbr>’s graduating class at
the commencement exercises of 1882.  Runkle quoted Rogers’s last words in a
memorial address delivered that same year:
</p>
<blockquote>
<p>“As I stand here today and see what the Institute is, … I call to mind
the beginnings of science.  I remember one hundred and fifty years ago Stephen
Hales published a pamphlet on the subject of illuminating gas, in which he
stated that his researches had demonstrated that 128 grains of bituminous coal
– ” “Bituminous coal,” these were his last words on earth.  Here he bent
forward, as if consulting some notes on the table before him, then slowly
regaining an erect position, threw up his hands, and was translated from the
scene of his earthly labors and triumphs to “the tomorrow of death,” where
the mysteries of life are solved, and the disembodied spirit finds unending
satisfaction in contemplating the new and still unfathomable mysteries of the
infinite future.
</p></blockquote>

<p>In the words of Francis A. Walker (<abbr>MIT</abbr>’s third president):
</p>
<blockquote>
<p>All his life he had borne himself most faithfully and heroically, and he died
as so good a knight would surely have wished, in harness, at his post, and in
the very part and act of public duty.
</p></blockquote>
</div>
<div id="FOOT90"><p><a class="footnote_backlink" href="#DOCF90"><sup>90</sup></a>
Equivalently, we could write
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> flipped-pairs
  </span><span class="opn">(</span><span class="pln">square-of-four 
   identity flip-vert identity flip-vert</span><span class="clo">))</span></pre></div>
</div>
<div id="FOOT91"><p><a class="footnote_backlink" href="#DOCF91"><sup>91</sup></a>
<code>Rotate180</code> rotates a
painter by 180 degrees (see <a href="#Exercise-2_002e50">Exercise 2.50</a>).  Instead of <code>rotate180</code>
we could say <code>(compose flip-vert flip-horiz)</code>, using the <code>compose</code>
procedure from <a href="1_002e3.xhtml#Exercise-1_002e42">Exercise 1.42</a>.</p>
</div>
<div id="FOOT92"><p><a class="footnote_backlink" href="#DOCF92"><sup>92</sup></a>
<code>Frame-coord-map</code> uses the vector operations described
in <a href="#Exercise-2_002e46">Exercise 2.46</a> below, which we assume have been implemented using some
representation for vectors.  Because of data abstraction, it doesn’t matter
what this vector representation is, so long as the vector operations behave
correctly.</p>
</div>
<div id="FOOT93"><p><a class="footnote_backlink" href="#DOCF93"><sup>93</sup></a>
<code>Segments-&gt;painter</code> uses the
representation for line segments described in <a href="#Exercise-2_002e48">Exercise 2.48</a> below.  It
also uses the <code>for-each</code> procedure described in <a href="#Exercise-2_002e23">Exercise 2.23</a>.</p>
</div>
<div id="FOOT94"><p><a class="footnote_backlink" href="#DOCF94"><sup>94</sup></a>
For example, the <code>rogers</code> painter of <a href="#Figure-2_002e11">Figure 2.11</a> was
constructed from a gray-level image.  For each point in a given frame, the
<code>rogers</code> painter determines the point in the image that is mapped to it
under the frame coordinate map, and shades it accordingly.  By allowing
different types of painters, we are capitalizing on the abstract data idea
discussed in <a href="2_002e1.xhtml#g_t2_002e1_002e3">2.1.3</a>, where we argued that a rational-number
representation could be anything at all that satisfies an appropriate
condition.  Here we’re using the fact that a painter can be implemented in any
way at all, so long as it draws something in the designated frame.  
<a href="2_002e1.xhtml#g_t2_002e1_002e3">2.1.3</a> also showed how pairs could be implemented as procedures.  Painters
are our second example of a procedural representation for data.</p>
</div>
<div id="FOOT95"><p><a class="footnote_backlink" href="#DOCF95"><sup>95</sup></a>
<code>Rotate90</code> is a pure rotation only for square frames,
because it also stretches and shrinks the image to fit into the rotated frame.</p>
</div>
<div id="FOOT96"><p><a class="footnote_backlink" href="#DOCF96"><sup>96</sup></a>
The diamond-shaped
images in <a href="#Figure-2_002e10">Figure 2.10</a> and <a href="#Figure-2_002e11">Figure 2.11</a> were created with
<code>squash-inwards</code> applied to <code>wave</code> and <code>rogers</code>.</p>
</div>
<div id="FOOT97"><p><a class="footnote_backlink" href="#DOCF97"><sup>97</sup></a>
Section <a href="3_002e3.xhtml#g_t3_002e3_002e4">3.3.4</a> describes one such language.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="2_002e3.xhtml#g_t2_002e3" accesskey="n" rel="next">2.3</a>, Prev: <a href="2_002e1.xhtml#g_t2_002e1" accesskey="p" rel="prev">2.1</a>, Up: <a href="#g_t2_002e2" accesskey="u" rel="prev">2.2</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>